Complete sets and closeness to complexity classes

DOI10.1007/BF01704904zbMath0617.68047OpenAlexW1971691873MaRDI QIDQ4727430

Uwe Schoening

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1007/bf01704904

zbMATH Keywords

polynomial timesparse setsbinary stringsBoolean closurepolynomially close

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items

Locating \(P\)/poly optimally in the extended low hierarchy ⋮ Robustness of PSPACE-complete sets ⋮ On intractability of the classUP ⋮ Notes on polynomial levelability ⋮ A refinement of the low and high hierarchies ⋮ On lower bounds of the closeness between complexity classes ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ The complexity of manipulative attacks in nearly single-peaked electorates ⋮ Reducibility classes of P-selective sets ⋮ A note on P-selective sets and closeness ⋮ Weak completeness in \(\text{E}\) and \(\text{E}_{2}\) ⋮ On polynomial time one-truth-table reducibility to a sparse set ⋮ The fault tolerance of NP-hard problems ⋮ Frequency of correctness versus average polynomial time ⋮ The Fault Tolerance of NP-Hard Problems ⋮ Exponential-time and subexponential-time sets ⋮ The opacity of backbones ⋮ Complexity classes between $\Theta _k^P$ and $\Delta _k^P$

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)