Computing functions with parallel queries to NP

AbstractThe class Θ2p of languages polynomial-time truth-table reducible to sets in NP has a wide range of different characterizations. We consider several functional versions of Θ2p based on these characterizations. We show that in this way the three function classes FLlogNP, FPlogNP, 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 FLlogNP coincides with any of the other classes then L = P, and that the equality of the classes FPlogNP 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 2nO(1/log log n)