• DocumentCode
    2200298
  • Title

    Computing functions with parallel queries to NP

  • Author

    Jenner, Birgit ; Torán, Jacobo

  • Author_Institution
    Fakultat fuer Inf., Tech. Univ. Munchen, Germany
  • fYear
    1993
  • fDate
    18-21 May 1993
  • Firstpage
    280
  • Lastpage
    291
  • Abstract
    The characterizations of the class Θ2p of languages polynomial-time truth-table reducible to sets in NP are surveyed studying the classes obtained when the characterizations are used to define functions instead of languages. It is shown that in this way three function classes are obtained. An overview of the known relationships between these classes, including some original results, is given
  • Keywords
    computability; computational complexity; formal languages; parallel algorithms; NP; function classes; languages; parallel queries; polynomial-time truth-table reducible; Complexity theory; Concurrent computing; Contracts; Jacobian matrices; Polynomials; Transducers;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
  • Conference_Location
    San Diego, CA
  • Print_ISBN
    0-8186-4070-7
  • Type

    conf

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