Title :
Computing functions with parallel queries to NP
Author :
Jenner, Birgit ; Torán, Jacobo
Author_Institution :
Fakultat fuer Inf., Tech. Univ. Munchen, Germany
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;
Conference_Titel :
Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
Conference_Location :
San Diego, CA
Print_ISBN :
0-8186-4070-7
DOI :
10.1109/SCT.1993.336519
