A note on complete problems for complexity classes

DOI10.1016/0020-0190(86)90078-5zbMath0634.68036OpenAlexW2064874002MaRDI QIDQ1097029

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)90078-5

zbMATH Keywords

oracle Turing machinespolynomial many-one reductibilitypolynomial Turing reducibility. recursive set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (4)

On the relative complexity of hard problems for complexity classes without complete problems ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Error-bounded probabilistic computations between MA and AM ⋮ Dot operators

Cites Work

• A comparison of polynomial time reducibilities
• The polynomial-time hierarchy
• On the complexity of unique solutions
• Strong reducibilities
• On the Structure of Polynomial Time Reducibility
• `` Strong NP-Completeness Results
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on complete problems for complexity classes