Power circuits, exponential algebra, and time complexity

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

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.

Original languageEnglish
Article number1250047
JournalInternational Journal of Algebra and Computation
Volume22
Issue number6
DOIs
StatePublished - Sep 2012

Keywords

  • Baumslag group
  • Highly compressed integers
  • exponential algebra
  • power circuits

Fingerprint

Dive into the research topics of 'Power circuits, exponential algebra, and time complexity'. Together they form a unique fingerprint.

Cite this