JavaScript is disabled for your browser. Some features of this site may not work without it.
Deterministic Polynomial Time O(log n) Queries

Author
Kadin, Jim
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]}$.
Date Issued
1986-08Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-771
Type
technical report