International Journal of Algebra and Computation · 2012 · 17 citations · 15 references
ComputingComputer ScienceMathematicsAlgebraAlgorithmsTheory Of ComputationAlgorithmic ComplexityCircuit ComplexityComplexity TheoryComputational AlgebraComputational ComplexityNumber-theoretic AlgorithmsCombinatorial Representation TheoryComplexity-theoretic ReductionsExponential SpaceExponentiation AlgorithmsPolynomial Time ComplexityPolynomial-time Algorithms
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.
15
Gaussian elimination is not optimal
Volker Strassen · Numerische Mathematik · 1969 · 2.5K citations
A Survey of Fast Exponentiation Methods
Daniel M. Gordon · Journal of Algorithms · 1998 · 534 citations
Achim Blumensath, Erich Grädel · 2002 · 292 citations