COMPUTING FUNCTIONS WITH PARALLEL QUERIES TO NP

The class Theta(2)(p) of languages polynomial-time truth-table reducib le to sets in NP has a wide range of different characterizations. We c onsider several functional versions of Theta(2)(p) based on these char acterizations. We show that in this way the three function classes FL( log)(NP),, FPlogNP, and FPparallel toNP are obtained. In contrast to t he language case the function classes seem to all be different. We giv e evidence in support of this fact by showing that FL(log)(NP) coincid es with any of the other classes then L=P, and that the equality of th e classes FPlogNP and FPparallel toNP would imply that the number of n ondeterministic bits needed for the computation of any problem in NP c an be reduced by a polylogarithmic factor, and that the problem can be computed deterministically with a subexponential time bound of order 2(no(1/log log n)).