\(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP

DOI10.1016/0022-0000(89)90024-XzbMath0693.68027MaRDI QIDQ908700

Jim Kadin

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

sparse complete setscollapse of the polynomial time hierarchyNP optimization problemsquery restricted oracle use

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items

On reductions of NP sets to sparse sets, Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete, Locating \(P\)/poly optimally in the extended low hierarchy, The complexity class θp2: Recent results and applications in AI and modal logic, Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP, A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison, On computing Boolean connectives of characteristic functions, Belief revision within fragments of propositional logic, The complexity of comparing optimal solutions, Upper bounds for the complexity of sparse and tally descriptions, Separating complexity classes with tally oracles, Weak cardinality theorems, On the complexity of propositional knowledge base revision, updates, and counterfactuals, On pseudorandomness and resource-bounded measure, Reductions to sets of low information content, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, Complexity classes between $\Theta _k^P$ and $\Delta _k^P$, Monotonous and randomized reductions to sparse sets, Computing properties of stable configurations of thermodynamic binding networks, Do there exist complete sets for promise classes?, Some structural properties of SAT, Kolmogorov characterizations of complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• Turing machines that take advice
• Some consequences of non-uniform conditions on uniform classes
• The complexity of facets (and some facets of complexity)
• Relativized circuit complexity
• The complexity of optimization problems
• A note on sparse oracles for NP
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• A comparison of polynomial time reducibilities
• The polynomial-time hierarchy
• Relativizing relativized computations
• On the unique satisfiability problem
• Bounded Query Classes
• On relativized exponential and probabilistic complexity classes
• On the complexity of unique solutions
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The Boolean Hierarchy I: Structural Properties
• On Isomorphisms and Density of $NP$ and Other Complete Sets