The theory of the polynomial many-one degrees of recursive sets is undecidable

DOI10.1007/3-540-55210-3_185zbMath1496.03171OpenAlexW1599138491MaRDI 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

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (3)

Uniformly hard languages. ⋮ Strong polynomial-time reducibility ⋮ Undecidability results for low complexity time classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: The theory of the polynomial many-one degrees of recursive sets is undecidable