The complexity of multiplying together n elements of a group G is studied. It is observed that as G ranges over a sequence of well-studied groups, the iterated multiplication problem is complete for corresponding well-studied complexity classes. Furthermore, the notion of completeness in question is extremely low-level and algebraic. The issue of uniformity is investigated.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
No takes yet. Share an insight, caveat, or question.
Immerman et al. (2003) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: