Complete sets and closeness to complexity classes

DOI10.1007/BF01704904MaRDI QIDQ4727430zbMATH OpenOpenAlexFDO

Authors Uwe Schöning

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

binary stringsBoolean closurepolynomial timepolynomially closesparse sets

Mathematics Subject Classification ID

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

Recommendations

• Closeness of NP-Hard Sets to Other Complexity Classes
• A note on P-selective sets and closeness
• A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
• A note on closeness between \(NP\)-hard sets and \(C_= P\)
• scientific article; zbMATH DE number 1500533

Cites work

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

Cited in

(31)

• Exotic quantifiers, complexity classes, and complete problems
• 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
• A note on closeness between \(NP\)-hard sets and \(C_= P\)
• The opacity of backbones
• A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
• Robustness of PSPACE-complete sets
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Completeness in approximation classes beyond APX
• Bounds on Quasi-Completeness
• On intractability of the classUP
• Singular coverings and non‐uniform notions of closed set computability
• The Fault Tolerance of NP-Hard Problems
• scientific article; zbMATH DE number 3985202 (Why is no real title available?)
• Near-Testable Sets
• On lower bounds of the closeness between complexity classes
• Closeness of NP-Hard Sets to Other Complexity Classes
• Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
• scientific article; zbMATH DE number 2101499 (Why is no real title available?)
• A refinement of the low and high hierarchies
• The complexity of manipulative attacks in nearly single-peaked electorates
• On polynomially \(\mathcal{D}\)-verbose sets
• The fault tolerance of NP-hard problems
• Complexity properties of recursively enumerable sets and bsQ-completeness
• Reducibility classes of P-selective sets
• A note on P-selective sets and closeness
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• A hierarchy for closed n-cell complements
• Frequency of correctness versus average polynomial time

This page was built for publication: Complete sets and closeness to complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4727430)