Splitting NP-Complete Sets

DOI10.1137/060673886MaRDI QIDQ3532575zbMATH OpenOpenAlexFDO

Authors Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang

Publication date 28 October 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/060673886

zbMATH Keywords

autoreducibilitycomputational and structural complexitymitoticityNP-complete sets

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Redundancy in Complete Sets
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• Mathematical Foundations of Computer Science 2005
• Autoreducibility, mitoticity, and immunity

Cited in

(20)

• Non-mitotic sets
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• Separation of NP-completeness notions
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• Introduction to autoreducibility and mitoticity
• scientific article; zbMATH DE number 3869312 (Why is no real title available?)
• Mitotic Classes in Inductive Inference
• scientific article; zbMATH DE number 3902038 (Why is no real title available?)
• scientific article; zbMATH DE number 1262805 (Why is no real title available?)
• scientific article; zbMATH DE number 512826 (Why is no real title available?)
• Splittings, Robustness, and Structure of Complete Sets
• Mitotic Classes
• Redundancy in Complete Sets
• Non-mitotic Sets
• Unions of disjoint NP-complete sets
• Theory and Applications of Models of Computation
• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
• SPLITTING NUMBER is NP-complete
• Polynomial-time axioms of choice and polynomial-time cardinality
• Splitting NP-complete sets infinitely

This page was built for publication: Splitting NP-Complete Sets

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