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

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

Mathematics Subject Classification ID

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