• DocumentCode
    2517513
  • Title

    The complexity of iterated multiplication

  • Author

    Immerman, Neil ; Landau, Susan

  • Author_Institution
    Dept. of Comput. Sci., Yale Univ., New Haven, CT, USA
  • fYear
    1989
  • fDate
    19-22 Jun 1989
  • Firstpage
    104
  • Lastpage
    111
  • Abstract
    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
  • Keywords
    computational complexity; digital arithmetic; completeness; complexity; complexity classes; iterated multiplication; iterated multiplication problem; uniformity; Circuits; Computer science; Mathematics; Polynomials; Symmetric matrices;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
  • Conference_Location
    Eugene, OR
  • Print_ISBN
    0-8186-1958-9
  • Type

    conf

  • DOI
    10.1109/SCT.1989.41816
  • Filename
    41816
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2517513