PNP[O(log n)] and sparse turing-complete sets for NP

摘要

PNP[O(log n)] is the class of languages recognizable by deterministic polynomial time machines that make O(log n) queries to an oracle for NP. Our main result is that if there exists a sparse set S ϵ NP such that co-NP (̄ NPs, then the polynomial hierarchy (PH) is contained in PNP[O(log n)]. Thus if there exists a sparse ⩾PT-complete set for NP, PH (̄ PNP[O(log n)]. We show that this collapse is optimal by showing for any function f (n) that is o(log n), there exists a relativized world where NP has a sparse ⩾PT-complete set and yet PNP[O(log n)] (̄/ PNP[f(n)]. We also discuss complete problems for PNP[O(log n)] and show languages related to the optimum solution size of Clique and K-SAT are ⩾Pm-complete. In related research, we investigate when the class of languages ⩾Pm-reducible to a set C equals PC[O(log n)]. We obtain results that allow us to prove that if DP is closed under complementation, then PNP[O(log n)] = DP.