#### Campus Units

Mathematics

#### Document Type

Article

#### Publication Version

Published Version

#### Publication Date

1990

#### Journal or Book Title

SIAM Journal on Computing

#### Volume

19

#### Issue

1

#### First Page

32

#### Last Page

43

#### DOI

10.1137/0219002

#### Abstract

A nonassociative algebra is nilpotent if there is some *n* such that the product of any *n* elements, no matter how they are associated, is zero. Several related, but more general, notions are left nilpotency, solvability, local nilpotency, and nillity. First the complexity of several decision problems for these properties is examined. In finite-dimensional algebras over a finite field it is shown that solvability and nilpotency can be decided in polynomial time. Over *Q*, nilpotency can be decided in polynomial time, while the algorithm for testing solvability uses a polynomial number of arithmetic operations, but is not polynomial time. Also presented is a polynomial time probabilistic algorithm for deciding left nillity. Then a problem involving algebras given by generators and relations is considered and shown to be NP-complete. Finally, a relation between local left nilpotency and a set of natural numbers that is 1-complete for the class $\Pi_{2}$ in the arithmetic hierarchy of recursion theory is demonstrated.

#### Copyright Owner

Society for Industrial and Applied Mathematics

#### Copyright Date

1990

#### Language

en

#### File Format

application/pdf

#### Recommended Citation

Hentzel, Irvin R. and Jacobs, David Pokrass, "Complexity and Unsolvability Properties of Nilpotency" (1990). *Mathematics Publications*. 140.

https://lib.dr.iastate.edu/math_pubs/140

## Comments

This article is published as Hentzel, Irvin Roy, and D. Pokrass Jacobs. "Complexity and unsolvability properties of nilpotency." SIAM Journal on Computing 19, no. 1 (1990): 32-43. doi:10.1137/0219002. Posted with permission.