Redundancy in Complete Sets

DOI10.1007/11672142_36MaRDI QIDQ5449820zbMATH OpenOpenAlexFDO

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

Publication date 19 March 2008

Published in STACS 2006 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Splitting NP-Complete Sets
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• Autoreducibility, mitoticity, and immunity
• Autoreducibility of complete sets for log-space and polynomial-time reductions
• Mathematical Foundations of Computer Science 2005

Cited in

(18)

• Non-mitotic sets
• Space-efficient informational redundancy
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• 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?)
• A Post's program for complexity theory.
• Splitting NP-Complete Sets
• The Fault Tolerance of NP-Hard Problems
• scientific article; zbMATH DE number 512826 (Why is no real title available?)
• Autoreducibility of complete sets for log-space and polynomial-time reductions
• Non-mitotic Sets
• Mathematical Foundations of Computer Science 2005
• The fault tolerance of NP-hard problems
• Theory and Applications of Models of Computation
• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
• Autoreducibility, mitoticity, and immunity
• The complexity of unions of disjoint sets

This page was built for publication: Redundancy in Complete Sets

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