The theory of the polynomial many-one degrees of recursive sets is undecidable
DOI10.1007/3-540-55210-3_185zbMATH Open1496.03171OpenAlexW1599138491MaRDI QIDQ5096783FDOQ5096783
Authors: Klaus Ambos-Spies, 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
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Undecidability and degrees of sets of sentences (03D35)
Cites Work
- Reducibility among combinatorial problems
- On the Structure of Polynomial Time Reducibility
- The complexity of theorem-proving procedures
- Sublattices of the polynomial time degrees
- Title not available (Why is that?)
- On the theory of the PTIME degrees of the recursive sets
- Decidability and Boolean representations
- The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
- The theory of the recursively enumerable weak truth-table degrees is undecidable
- Honest polynomial time reducibilities and the \(P=?NP\) problem
- Title not available (Why is that?)
- Polynomial and abstract subrecursive classes
- On the structure of sets in NP and other complexity classes
- Title not available (Why is that?)
- Title not available (Why is that?)
- An Inhomogeneity in the Structure of Karp Degrees
- The structure of the honest polynomial m-degrees
Cited In (3)
This page was built for publication: The theory of the polynomial many-one degrees of recursive sets is undecidable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096783)
