Academic
Publications
Functions Computable with Nonadaptive Queries to NP

Functions Computable with Nonadaptive Queries to NP,10.1007/s002240000079,Theory of Computing Systems / Mathematical Systems Theory,Harry Buhrman,Jim

Functions Computable with Nonadaptive Queries to NP   (Citations: 9)
BibTex | RIS | RefWorks Download
.    We study FP|| NP , the class of functions that can be computed in polynomial time 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|| 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|| NP . Moreover, we characterize FP|| NP as the class of functions that reduces to such optimization functions. We call this property strong hardness. The main question is whether these function classes are complete for FP|| NP . That is, whether it is possible to compute an optimal value for a given optimization problem in FP|| NP . We show that these optimization problems are complete for FP|| NP , if and only if one can compute membership proofs for NP sets in FP|| NP . This indicates that the completeness question is a hard one.
Journal: Theory of Computing Systems / Mathematical Systems Theory - MST , vol. 31, no. 1, pp. 77-92, 1998
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...One can for the same reason strengthen to a PH = SNP∩coNP 2 conclusion a closely related theorem, namely, the result of Buhrman, Kadin, and Thierauf [BKT98] that if, in a certain model of access to partial functions, the solution function of some “universal relation [AB92]” is computable in the class “FPNPSV[1],” then PH = NPNP...

    Jin-yi Caiet al. Competing Provers Yield Improved Karp-Lipton Collapse Results

    • ... In fact, it is at least plausible to conjecture that NPcomplete sets may have even more in common than mere isomorphism (and, indeed, many natural sets do have more in common), and many papers have wondered just what that “more” may be. One could say that this general type of intuition has led people to such notions as structure-preserving reductions [LL78,ADP80], witness-isomorphic reductions [FHT97], universal relations [AB92,Bis95, ...

    Unknown. Take-home complexity

Sort by: