Non-mitotic Sets

DOI10.1007/978-3-540-77050-3_12zbMath1135.68425OpenAlexW2143555208MaRDI QIDQ5458830

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

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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (2)

Non-uniform reductions ⋮ Space-efficient informational redundancy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Diagonalizations over polynomial time computable sets
• Reductions on NP and p-selective sets
• On being incoherent without being very hard
• A comparison of polynomial time reducibilities
• \(p\)-selective self-reducible sets: a new characterization of P
• Relativized counting classes: Relations among thresholds, parity, and mods
• Separation of NP-Completeness Notions
• Comparing Reductions to NP-Complete Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Splittings, Robustness, and Structure of Complete Sets
• Mitotic recursively enumerable sets
• Redundancy in Complete Sets

This page was built for publication: Non-mitotic Sets