The theory of the polynomial many-one degrees of recursive sets is undecidable
From MaRDI portal
Publication:5096783
DOI10.1007/3-540-55210-3_185zbMath1496.03171MaRDI QIDQ5096783
Ambos-Spies, Klaus, André Nies
Publication date: 18 August 2022
Published in: STACS 92 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-55210-3_185
03D35: Undecidability and degrees of sets of sentences
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03D30: Other degrees and reducibilities in computability and recursion theory
Related Items
Strong polynomial-time reducibility, Undecidability results for low complexity time classes, Uniformly hard languages.
Cites Work
- On the theory of the PTIME degrees of the recursive sets
- Honest polynomial time reducibilities and the \(P=?NP\) problem
- On the structure of sets in NP and other complexity classes
- The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
- Polynomial and abstract subrecursive classes
- The structure of the honest polynomial m-degrees
- Sublattices of the polynomial time degrees
- An Inhomogeneity in the Structure of Karp Degrees
- Decidability and Boolean representations
- The theory of the recursively enumerable weak truth-table degrees is undecidable
- On the Structure of Polynomial Time Reducibility
- Reducibility among Combinatorial Problems
- The complexity of theorem-proving procedures
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item