FUNCTIONS COMPUTABLE WITH NONADAPTIVE QUERIES TO NP

We study FPparallel toNP, the class of functions that can be computed in polynomial time with nonadaptive queries to an NP oracle, This is m otivated by the question of whether it is possible to compute witnesse s for NP sets within FPparallel toNP. The known algorithms for this ta sk all require sequential access to the oracle. On the other hand, the re is no evidence known yet that this should not be possible with para llel queries. We define a class of optimization problems based on NP s ets, where the optimum is taken over a polynomially bounded range (NPb Opt). We show that if such an optimization problem is based on one of the known NP-complete sets, then it is hard for FPparallel toNP. Moreo ver, we characterize FPparallel toNP as the class of functions that re duces to such optimization functions, We call this property strong har dness. The main question is whether these function classes are complet e for FPparallel toNP. That is, whether it is possible to compute an o ptimal value for a given optimization problem in FPparallel toNP. We s how that these optimization problems are complete for FPparallel toNP, if and only if one can compute membership proofs for NP sets in FPpar allel toNP. This indicates that the completeness question is a hard on e.