A note on complete problems for complexity classes
From MaRDI portal
Publication:1097029
DOI10.1016/0020-0190(86)90078-5zbMath0634.68036OpenAlexW2064874002MaRDI QIDQ1097029
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
oracle Turing machinespolynomial many-one reductibilitypolynomial Turing reducibility. recursive set
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