Complete sets and closeness to complexity classes

DOI10.1007/BF01704904zbMath0617.68047MaRDI QIDQ4727430

Uwe Schoening

Publication date: 1986

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

polynomial time; sparse sets; binary strings; Boolean closure; polynomially close

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D60: Computability and recursion theory on ordinals, admissible sets, etc.

Related Items

Complexity classes between $\Theta _k^P$ and $\Delta _k^P$, A refinement of the low and high hierarchies, The fault tolerance of NP-hard problems, Reducibility classes of P-selective sets, A note on P-selective sets and closeness, Weak completeness in \(\text{E}\) and \(\text{E}_{2}\), Frequency of correctness versus average polynomial time, Notes on polynomial levelability, On polynomial time one-truth-table reducibility to a sparse set, Exponential-time and subexponential-time sets, Locating \(P\)/poly optimally in the extended low hierarchy, Robustness of PSPACE-complete sets, On intractability of the classUP, The Fault Tolerance of NP-Hard Problems, On lower bounds of the closeness between complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A low and a high hierarchy within NP
• Strong nondeterministic polynomial-time reducibilities
• A note on sparse oracles for NP
• Reductions on NP and p-selective sets
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy
• Circuit-size lower bounds and non-reducibility to sparse sets
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• Bi-immune sets for complexity classes
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Polynomial Time Enumeration Reducibility
• Degrees of Unsolvability. (AM-55)