Autoreducibility, mitoticity, and immunity
From MaRDI portal
Publication:881593
DOI10.1016/j.jcss.2006.10.020zbMath1115.68087OpenAlexW2030692444MaRDI QIDQ881593
A. Pavan, Christian Glaßer, Liyu Zhang, Ogihara, Mitsunori, Selman, Alan L.
Publication date: 30 May 2007
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2006.10.020
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Autoreducibility and mitoticity of logspace-complete sets for NP and other classes, Polynomial-time axioms of choice and polynomial-time cardinality, Introduction to Autoreducibility and Mitoticity, Autoreducibility of NP-complete sets under strong hypotheses, Machines that can output empty words, Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity and structure
- Diagonalizations over polynomial time computable sets
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- On being incoherent without being very hard
- Relative complexity of checking and evaluating
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Exponential-time and subexponential-time sets
- Probabilistic complexity classes and lowness
- Genericity and measure for exponential time
- Separation of NP-Completeness Notions
- On the unique satisfiability problem
- Properties of NP‐Complete Sets
- Bi-immune sets for complexity classes
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
- Complete Problems and Strong Polynomial Reducibilities
- A Completely Mitotic Nonrecursive R.E. Degree
- Splittings, Robustness, and Structure of Complete Sets
- On Existentially First-Order Definable Languages and Their Relation to NP
- Mitotic recursively enumerable sets
- The Complexity and Distribution of Hard Problems
- Separating Complexity Classes Using Autoreducibility
- Redundancy in Complete Sets
- Mathematical Foundations of Computer Science 2005
- The Priority Method I
- Machines, Computations, and Universality
- Developments in Language Theory
- Counting classes: Thresholds, parity, mods, and fewness
- Computability and complexity theory
