A note on a theorem by Ladner

DOI10.1016/0020-0190(82)90113-2zbMath0515.03022OpenAlexW1984577660MaRDI QIDQ1051633

Josep Diaz, José L. Balcázar

Publication date: 1982

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

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

zbMATH Keywords

equivalencereducibilityNP-completeincomparableNPP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Hierarchies of computability and definability (03D55)

Related Items

Uniformly hard languages. ⋮ If not empty, NP-P is topologically large ⋮ Properties of uniformly hard languages

Cites Work

• Unnamed Item
• A comparison of polynomial time reducibilities
• On the Structure of Polynomial Time Reducibility
• Two-Processor Scheduling with Start-Times and Deadlines