Autoreducibility, mitoticity, and immunity

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

zbMATH Keywords

immunitycomplete setsautoreducibilitymitoticityweak mitoticity

Mathematics Subject Classification ID

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