{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:33:15Z","timestamp":1787340795426,"version":"build-2736575974"},"reference-count":12,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1990,2]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/0219002","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:33:47Z","timestamp":1109226827000},"page":"32-43","source":"Crossref","is-referenced-by-count":2,"title":["Complexity and Unsolvability Properties of Nilpotency"],"prefix":"10.1137","volume":"19","author":[{"given":"I. R.","family":"Hentzel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D. Pokrass","family":"Jacobs","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","volume-title":"Computability, complexity, and languages","author":"Davis M.","year":"1983"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02080331"},{"key":"R3","first-page":"147","volume":"15","author":"Dorofeyev G. V.","year":"1960","journal-title":"Uspekhi Mat. Nauk"},{"key":"R4","unstructured":"K. Friedl, L. Ronyai,  Polynomial time solutions of some problems in computational algebra,  Proc. 17th Annual ACM Symposium on Theory of Computing, Providence, RI,  1985 0927.68121"},{"key":"R5","volume-title":"Computers and intractability","author":"Garey M.","year":"1979"},{"key":"R6","first-page":"241","volume":"62","author":"Hentzel I. R.","year":"1988","journal-title":"Congr. Numer."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"I. R. Hentzel, D. J. Pokrass,  Verification of non-identities in algebras,  Proc. 1988 International Symposium on Symbolic and Algebraic Computation, Springer-Verlag, Berlin, New York,  1989","DOI":"10.1007\/3-540-51084-2_48"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(77)90279-4"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"L. Ronyai,  Simple algebras are difficult,  Proc. 19th Annual ACM Symposium on Theory of Computing, New York,  1987","DOI":"10.1145\/28395.28438"},{"key":"R10","volume-title":"An introduction to nonassociative algebras","author":"Schafer R.","year":"1966"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0219002","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:48:30Z","timestamp":1787338110000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0219002"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,2]]},"references-count":12,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1990,2]]}},"alternative-id":["10.1137\/0219002"],"URL":"https:\/\/doi.org\/10.1137\/0219002","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,2]]}}}