Non-mitotic Sets

DOI10.1007/978-3-540-77050-3_12MaRDI QIDQ5458830zbMATH OpenOpenAlexFDO

Authors Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang

Publication date 24 April 2008

Published in FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77050-3_12

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Non-mitotic sets
• Splitting NP-Complete Sets
• Redundancy in Complete Sets
• scientific article; zbMATH DE number 3869312
• Mathematical Foundations of Computer Science 2005

Cites work

• p-selective self-reducible sets: a new characterization of P
• A comparison of polynomial time reducibilities
• Comparing Reductions to NP-Complete Sets
• Diagonalizations over polynomial time computable sets
• scientific article; zbMATH DE number 3869312 (Why is no real title available?)
• scientific article; zbMATH DE number 1072532 (Why is no real title available?)
• scientific article; zbMATH DE number 6472645 (Why is no real title available?)
• Mitotic recursively enumerable sets
• On being incoherent without being very hard
• On Isomorphisms and Density of NP and Other Complete Sets
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Reductions on NP and p-selective sets
• Redundancy in Complete Sets
• Relativized counting classes: Relations among thresholds, parity, and mods
• Separation of NP-completeness notions
• Splittings, Robustness, and Structure of Complete Sets

Cited in

(7)

• Non-mitotic sets
• Non-uniform reductions
• Space-efficient informational redundancy
• Introduction to autoreducibility and mitoticity
• scientific article; zbMATH DE number 3869312 (Why is no real title available?)
• Examples of non-shy sets
• Theory and Applications of Models of Computation

This page was built for publication: Non-mitotic Sets

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