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

DOI10.1007/3-540-55210-3_185MaRDI QIDQ5096783zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

• scientific article; zbMATH DE number 3869313 (Why is no real title available?)
• scientific article; zbMATH DE number 3817684 (Why is no real title available?)
• scientific article; zbMATH DE number 3966058 (Why is no real title available?)
• scientific article; zbMATH DE number 4037840 (Why is no real title available?)
• An Inhomogeneity in the Structure of Karp Degrees
• Decidability and Boolean representations
• Honest polynomial time reducibilities and the \(P=?NP\) problem
• On the Structure of Polynomial Time Reducibility
• On the structure of sets in NP and other complexity classes
• On the theory of the PTIME degrees of the recursive sets
• Polynomial and abstract subrecursive classes
• Reducibility among combinatorial problems
• Sublattices of the polynomial time degrees
• The complexity of theorem-proving procedures
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• The structure of the honest polynomial m-degrees
• The theory of the recursively enumerable weak truth-table degrees is undecidable

Cited in

(3)

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

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)