P^NP[O( n)] and sparse turing-complete sets for NP
It has been known (\textit{S. Mahaney} [J. Comput. Syst. Sci. 25, 130-143 (1987; Zbl 0493.68043)] that the polynomial hierarchy collapses to \(P^{NP}\) if NP has a \(\leq^ P_ T\)-complete sparse set. The author improves this result by replacing \(N^{NP}\) with \(P^{NP[O(\log n)]}\), where this latter class is the class of all languages acceptable by deterministic polynomial time machines making only O(log n) queries to an NP-oracle. This result is a consequence of the following one: If for a sparse S in NP it holds that \(coNP\subseteq NP^ S\), then \(PH\subseteq P^{NP[O(\log n)]}\). This collapse result is optimal in the following sense: For any function \(f(n)=o(\log n)\) there exists a set B for which \(NP^ B\) has a sparse \(\leq^ P_ T\)-complete set and \((P^ B)^{NP^ B[O(\log n)]}\subseteq (P^ B)^{NP^ B[f(n)]}.\) Furthermore, the paper exhibits \(\leq^ P_ m\)-complete problems for \(P^{NP[O(\log n)]}\) and discusses conditions fo the class of languages \(\leq^ P_ m\)-reducible to a set C to be equal to \(P^{C[O(\log n)]}\). For \(D^ P=\{X\cap Y :\) \(X\in NP\wedge Y\in coNP\}\) it is shown: If \(D^ P=coD^ P\), then \(P^{NP[O(\log n)]}\subseteq D^ P\).
- A comparison of polynomial time reducibilities
- A note on sparse oracles for NP
- Bounded Query Classes
- scientific article; zbMATH DE number 4024790 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3799016 (Why is no real title available?)
- On Isomorphisms and Density of NP and Other Complete Sets
- On relativized exponential and probabilistic complexity classes
- On the complexity of unique solutions
- On the unique satisfiability problem
- Relativized circuit complexity
- Relativizing relativized computations
- Some consequences of non-uniform conditions on uniform classes
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The Boolean Hierarchy I: Structural Properties
- The complexity of facets (and some facets of complexity)
- The complexity of optimization problems
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- The polynomial-time hierarchy
- The strong exponential hierarchy collapses
- Turing machines that take advice
- A note on complete problems for complexity classes
- Separating complexity classes with tally oracles
- On the complexity of propositional knowledge base revision, updates, and counterfactuals
- On reductions of NP sets to sparse sets
- Locating P/poly optimally in the extended low hierarchy
- Some structural properties of SAT
- Computing properties of stable configurations of thermodynamic binding networks
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
- The complexity of comparing optimal solutions
- There are no sparse NP\(_{w}\)-hard sets
- The polynomial-time hierarchy and sparse oracles
- Do there exist complete sets for promise classes?
- scientific article; zbMATH DE number 3883613 (Why is no real title available?)
- On Sparse Complete Sets
- Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
- scientific article; zbMATH DE number 3921977 (Why is no real title available?)
- scientific article; zbMATH DE number 4106271 (Why is no real title available?)
- Belief revision within fragments of propositional logic
- Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
- scientific article; zbMATH DE number 1107624 (Why is no real title available?)
- Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
- Monotonous and randomized reductions to sparse sets
- scientific article; zbMATH DE number 1834655 (Why is no real title available?)
- On computing Boolean connectives of characteristic functions
- Upper bounds for the complexity of sparse and tally descriptions
- The complexity class θp2: Recent results and applications in AI and modal logic
- Reductions to sets of low information content (extended abstract)
- Weak cardinality theorems
- On pseudorandomness and resource-bounded measure
- Kolmogorov characterizations of complexity classes
This page was built for publication: \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908700)
