Deterministic Polynomial Time O(log n) Queries

Abstract

$P^{NP[\log n]}$ is the class of languages recognizable by determining polynomial time machines that make $O(\log n)$ queries to an oracle for NP. Many of the languages related to optimal solution sizes of NP optimization problems are members of this class. We relate $P^{NP[\log n]}$ to the study of sparse oracles for NP by showing that if NP has a sparse $\leq^{P}_{T}$-complete set, then the polynomial time hierarchy collapses to $P^{NP[\log n]}$. We also discuss complete problems and show that UOCSAT, the set of CNF formulas with the property that every assignment that satisfies the maximum number of clauses satisfies the same set of clauses, is $\leq^{P}_{m}$-complete for $P^{NP[\log n]}$.