Functions Computable with Nonadaptive Queries to NP
Functions Computable with Nonadaptive Queries to NP
复制标题
可通过对 NP 的非自适应查询进行计算的函数
DOI：
10.1007/s002240000079
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
T. Thierauf
中科院分区：
文献类型：
--
作者：
H. Buhrman;Jim Kadin;T. Thierauf
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 theknownNP-complete sets, then it is hard for FP||NP. Moreover, wecharacterizeFP||NPas the class of functions that reduces to such optimization functions. We call this propertystrong 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.
