Non-mitotic sets

DOI10.1016/j.tcs.2008.12.043zbMath1191.68333OpenAlexW2025164891MaRDI QIDQ1019177

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

Publication date: 28 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.12.043

zbMATH Keywords

computational complexityautoreducibilitymitoticity

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

Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets

Cites Work

• 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
• Splitting NP-Complete Sets
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item