TY - JOUR
T1 - Power circuits, exponential algebra, and time complexity
AU - Miasnikov, Alexei G.
AU - Ushakov, Alexander
AU - Won, Dong Wook
PY - 2012/9
Y1 - 2012/9
N2 - Motivated by algorithmic problems from combinatorial group theory we study computational properties of integers equipped with binary operations +, -, z = x · 2 y, z = x · 2 -y (the former two are partial) and predicates < 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 · 2 y, 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.
AB - Motivated by algorithmic problems from combinatorial group theory we study computational properties of integers equipped with binary operations +, -, z = x · 2 y, z = x · 2 -y (the former two are partial) and predicates < 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 · 2 y, 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.
KW - Baumslag group
KW - Highly compressed integers
KW - exponential algebra
KW - power circuits
UR - http://www.scopus.com/inward/record.url?scp=84865722341&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84865722341&partnerID=8YFLogxK
U2 - 10.1142/S0218196712500476
DO - 10.1142/S0218196712500476
M3 - Article
AN - SCOPUS:84865722341
SN - 0218-1967
VL - 22
JO - International Journal of Algebra and Computation
JF - International Journal of Algebra and Computation
IS - 6
M1 - 1250047
ER -