On functions computable with nonadaptive queries to NP
Harry Buhrman, Jim Kadin, Thomas Thierauf · 2002
We study FP/sub /spl par/sup NP/, the class of functions that can be computed with nonadaptive queries to an NP oracle. We show that optimization problems stemming from the known NP complete sets, where the optimum is taken over a polynomially bounded range, are hard for FP/sub /spl par/sup NP/. This is related to (and, in some sense, extends) work of Z. Chen and S. Toda (1991). In addition, it turns out that these optimization problems are all equivalent under a certain functional reducibility. By studying the question whether these function classes are complete for FP/sub /spl par/sup NP/, i.e. whether it is possible to compute an optimal value for a given optimization problem in FP/sub /spl par/sup NP/, we show that this is exactly as hard as to compute membership proofs for NP complete sets in FP/sub /spl par/sup NP/. On the other hand, FP/sub /spl par/sup NP/ can be characterized as the class of functions that reduces to the above mentioned optimization functions. We call this property quasi-completeness. A subclass of FP/sub /spl par/sup NP/ is NPSV, the class of functions that can be computed by single-valued NP transducers, We exhibit function classes that are quasi-complete for NPSV but not complete unless the polynomial time hierarchy collapses.>