Paper Info
Title
Computing functions with parallel queries to NP
Abstract
The class Θ 2 p of languages polynomial-time truth-table reducible to sets in NP has a wide range of different characterizations. We consider several functional versions of Θ 2 p based on these characterizations. We show that in this way the three function classes FL log NP , FP log NP , and FP ∥ NP are obtained. In contrast to the language case the function classes seem to all be different. We give evidence in support of this fact by showing that FL log NP coincides with any of the other classes then L = P , and that the equality of the classes FP log NP and FP ∥ NP would imply that the number of nondeterministic bits needed for the computation of any problem in NP can be reduced by a polylogarithmic factor, and that the problem can be computed deterministically with a subexponential time bound of order 2 n O (1/ log log n ) .
Year
DOI
Venue
1993
10.1016/0304-3975(94)00080-3
Theor. Comput. Sci.
Keywords
DocType
Volume
computing function,parallel query,polynomials,polynomial time,computational complexity,formal languages,computability,parallel algorithms,transducers,languages,concurrent computing,np
Conference
141
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
31
PageRank 
References 
Authors
1.82
18
2
Name
Order
Citations
PageRank
Birgit Jenner124714.47
Jacobo Torán256449.26