Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets

DOI10.1016/0020-0190(86)90054-2zbMath0592.03028OpenAlexW2007469118MaRDI QIDQ1075319

Ambos-Spies, Klaus

Publication date: 1986

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90054-2

zbMATH Keywords

polynomial-time reducibilitiesNP-setsprincipal ideals of polynomial-time degrees of recursive sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (5)

Polynomial terse sets ⋮ Automorphisms in the PTIME-Turing degrees of recursive sets ⋮ On the structures inside truth-table degrees ⋮ Undecidability results for low complexity time classes ⋮ Effectively dense Boolean algebras and their applications

Cites Work

• Unnamed Item
• A note on structure and looking back applied to the relative complexity of computable functions
• On the structure of sets in NP and other complexity classes
• A comparison of polynomial time reducibilities
• On the Structure of Polynomial Time Reducibility

This page was built for publication: Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets