Mathematics – Group Theory
Scientific paper
2010-06-13
Mathematics
Group Theory
Scientific paper
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 x2^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, as well as the word problems in some "hard to crack" one-relator groups.
Myasnikov Alexei G.
Ushakov Alexander
Won Dong Wook
No associations
LandOfFree
Power Circuits, Exponential Algebra, and Time Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Power Circuits, Exponential Algebra, and Time Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Power Circuits, Exponential Algebra, and Time Complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-421277