POWER CIRCUITS, EXPONENTIAL ALGEBRA, AND TIME COMPLEXITY

DOI10.1142/S0218196712500476zbMath1285.03052arXiv1006.2570OpenAlexW2963314138MaRDI QIDQ4649509

Alexander Ushakov, Dong Wook Won, Alexei G. Myasnikov

Publication date: 22 November 2012

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1006.2570

zbMATH Keywords

Baumslag grouppower circuitsexponential algebrahighly compressed integers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

On efficiency of notations for natural numbers, Taming the hydra: The word problem and extreme integer compression, Parallel algorithms for power circuits and the word problem of the Baumslag group, The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable., Improved parallel algorithms for generalized Baumslag groups, Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P, Unnamed Item, Unnamed Item, Conjugacy in Baumslag's group, generic case complexity, and division in power circuits, Complexity of word problems for HNN-extensions, The conjugacy problem for Higman’s group, Compression techniques in group theory

Cites Work

• Unnamed Item
• Pseudo-exponentiation on algebraically closed fields of characteristic zero
• Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
• Equational theory of positive numbers with exponentiation is not finitely axiomatizable
• Exponential rings, exponential polynomials and exponential functions
• Schanuel's conjecture and free exponential rings
• Gaussian elimination is not optimal
• A Survey of Fast Exponentiation Methods
• Computational Complexity
• Solution of the identity problem for integral exponential functions
• A non-cyclic one-relator group all of whose finite quotients are cyclic
• Minimality and other properties of the width-𝑤 nonadjacent form