{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T18:30:05Z","timestamp":1778783405012,"version":"3.51.4"},"reference-count":27,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2012,9]]},"abstract":"<jats:p>Motivated by algorithmic problems from combinatorial group theory we study computational properties of integers equipped with binary operations +, -, z = x \u22c5 2<jats:sup>y<\/jats:sup>, z = x \u22c5 2<jats:sup>-y<\/jats:sup>(the former two are partial) and predicates &lt; and =. Notice that in this case very large numbers, which are obtained as n towers of exponentiation in the base 2 can be realized as n applications of the operation x \u22c5 2<jats:sup>y<\/jats:sup>, so working with such numbers given in the usual binary expansions requires super exponential space. We define a new compressed representation for integers by power circuits (a particular type of straight-line programs) which is unique and easily computable, and show that the operations above can be performed in polynomial time if the numbers are presented by power circuits. We mention several applications of this technique to algorithmic problems, in particular, we prove that the quantifier-free theories of various exponential algebras are decidable in polynomial time.<\/jats:p>","DOI":"10.1142\/s0218196712500476","type":"journal-article","created":{"date-parts":[[2012,5,14]],"date-time":"2012-05-14T01:45:23Z","timestamp":1336959923000},"page":"1250047","source":"Crossref","is-referenced-by-count":8,"title":["POWER CIRCUITS, EXPONENTIAL ALGEBRA, AND TIME COMPLEXITY"],"prefix":"10.1142","volume":"22","author":[{"given":"ALEXEI G.","family":"MIASNIKOV","sequence":"first","affiliation":[{"name":"Department of Mathematics, Stevens Institute of Technology, Hoboken, NJ 07030, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEXANDER","family":"USHAKOV","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Stevens Institute of Technology, Hoboken, NJ 07030, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DONG WOOK","family":"WON","sequence":"additional","affiliation":[{"name":"Department of Mathematics, LaGuardia College, Queens, NY 11101, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,8,31]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700007783"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0265-3"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8"},{"key":"rf6","volume-title":"What are Numbers and What Should They be?","author":"Dedekind R.","year":"1995"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9730-4_9"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0913"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90049-8"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-004-0570-x"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_76"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0095664"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90017-G"},{"key":"rf15","unstructured":"A.\u00a0Macintyre and A.\u00a0Wilkie, Kreiseliana: About and Around Georg Kreisel (AK Peters, 1996)\u00a0pp. 441\u2013467."},{"key":"rf16","first-page":"3","volume":"16","author":"Malcev A. I.","journal-title":"Uspekhi Mat. Nauk"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-05-01769-2"},{"key":"rf20","first-page":"12","author":"Platonov A. N.","journal-title":"Vestnik Moskov. Univ. Ser. I Mat. Mekh. (3)"},{"key":"rf21","first-page":"341","volume":"94","author":"Rabin M.","journal-title":"Trans. Amer. Math. Soc."},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19690152003"},{"key":"rf23","first-page":"46","volume":"28","author":"Richardson D.","journal-title":"Bull. London Math. Soc. (2)"},{"key":"rf25","doi-asserted-by":"crossref","first-page":"741","DOI":"10.4171\/cmh\/142","volume":"83","author":"Schleimer S.","journal-title":"Comment. Math. Helv."},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb03624.x"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"rf28","unstructured":"V.\u00a0Strassen, Handbook of Theoretical Computer Science, Lecture Notes in Computer Science\u00a0A, ed. J.\u00a0van Leeuwen (Elsevier, 1990)\u00a0pp. 633\u2013673."},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1984.113.51"},{"key":"rf30","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1215\/ijm\/1256052287","volume":"16","author":"Weinbaum C. M.","journal-title":"Illinois J. Math."},{"key":"rf31","first-page":"107","volume":"6","author":"Wilkie A. J.","journal-title":"Quad. Mat."},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.07.001"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196712500476","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T14:46:44Z","timestamp":1713970004000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196712500476"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,31]]},"references-count":27,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2012,8,31]]},"published-print":{"date-parts":[[2012,9]]}},"alternative-id":["10.1142\/S0218196712500476"],"URL":"https:\/\/doi.org\/10.1142\/s0218196712500476","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,31]]}}}