P NP [log n] and Sparse Turing-Complete Sets for NP
Jim Kadin · 1987
pNP[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[log n]. Thus if there exists a sparse ≤$_\text{T}^\text{P}$-complete set for NP, PH ⊆ PNP[log n]We show that this collapse is optimal by showing for any function f(n) with f(n)$_\text{T}^\text{P}$-complete set and yet PNP[log n]⊈ PNP[f(n)]. We also discuss complete problems for PNP[log n]and show languages related to the optimal solution size of Clique and K-SAT are ≤$_\text{m}^\text{p}$-complete. In related research, we give a characterization of the sets C for which PC[log n]equals the class of languages ≤$_\text{m}^\text{p}$-reducible to C.