We study FP_{tt}^{NP}, the class of functions that can be computed with nonadaptive queries to an NP oracle. This is motivated by the question of whether it is possible to compute witnesses for NP sets within FP_{tt}^{NP}. The known algorithms for this task all require sequential access to the oracle. On the other hand, there is no evidence known yet that this should not be possible with parallel queries.

We define a class of optimization problems based on NP sets,
where the optimum is taken over a polynomially bounded range (NPbOpt).
We show that if such an optimization problem is based on
one of the *known* NP complete sets,
then it is hard for FP_{tt}^{NP}.
Moreover,
we will *characterize*
FP_{tt}^{NP} as the class of functions
that reduces to such optimization functions.
We will call this property *strong hardness*.

The main question is whether these function classes are
complete for FP_{tt}^{NP}.
That is,
whether it is possible to compute
an optimal value for a given optimization problem in FP_{tt}^{NP}.
We show that these optimization problems are
complete for FP_{tt}^{NP}, if and only if
one can
compute membership proofs for NP sets in FP_{tt}^{NP}.
This indicates that the completeness question is a hard one.