Introduction to Autoreducibility and Mitoticity
DOI10.1007/978-3-319-50062-1_5zbMath1376.03042OpenAlexW2559610214MaRDI QIDQ2973718
Selman, Alan L., Maximilian Witek, Christian Glaßer, Dung Tien Nguyen
Publication date: 4 April 2017
Published in: Computability and Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-50062-1_5
computational complexityrecursion theoryrecursively enumerable setsreducibilitiesautoreducibilitymitoticity
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items (3)
Cites Work
- Unnamed Item
- Unnamed Item
- Friedberg splittings of recursively enumerable sets
- Autoreducibility, mitoticity, and immunity
- Completely mitotic r. e. degrees
- On being incoherent without being very hard
- Splitting theorems and the jump operator
- Splitting theorems in recursion theory
- Splitting NP-Complete Sets
- The Degrees of R.E. Sets Without the Universal Splitting Property
- Splitting properties of r.e. sets and degrees
- Degrees of Splittings and Bases of Recursively Enumerable Subspace
- Minimal degrees for polynomial reducibilities
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Completeness for nondeterministic complexity classes
- Complete Problems and Strong Polynomial Reducibilities
- On the Universal Splitting Property
- Mitotic recursively enumerable sets
- Separating Complexity Classes Using Autoreducibility
- Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions
- Creative sets
This page was built for publication: Introduction to Autoreducibility and Mitoticity
