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.

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.

Copyright Owner

Society for Industrial and Applied Mathematics

Language

en

File Format

application/pdf

Included in

Algebra Commons

Share

COinS