Mathematical Foundations of Computer Science 2005

DOI10.1007/11549345MaRDI QIDQ5492874zbMATH OpenOpenAlexFDO

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

Publication date 20 October 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

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

• Autoreducibility, mitoticity, and immunity
• Redundancy in Complete Sets
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• Autoreducibility of complete sets for log-space and polynomial-time reductions
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes

Cited in

(12)

• Query-monotonic Turing reductions
• Probabilistic autoreductions
• Properties of NP‐Complete Sets
• Splitting NP-Complete Sets
• Strong self-reducibility precludes strong immunity
• Autoreducibility of complete sets for log-space and polynomial-time reductions
• Redundancy in Complete Sets
• Non-mitotic Sets
• Theory and Applications of Models of Computation
• Autoreducibility, mitoticity, and immunity
• On the autoreducibility of functions
• Pushdown dimension

This page was built for publication: Mathematical Foundations of Computer Science 2005

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