2010/06/13 by Alexei Myasnikov, Alexei G. Myasnikov, Myasnikov, Alexei G. +4 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR) #cs.CC #math.GR #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1006.2570
arxiv created 2010/06/13 · openalex publication_date 2010/06/13 · arxiv updated 2010/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by algorithmic problems from combinatorial group theory we study computational properties of integers equipped with binary operations +, -, z = x 2y, 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 x2y, 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, as well as the word problems in some "hard to crack" one-relator groups.