A note on complete problems for complexity classes
From MaRDI portal
Publication:1097029
DOI10.1016/0020-0190(86)90078-5zbMath0634.68036MaRDI 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 machines; polynomial many-one reductibility; polynomial Turing reducibility. recursive set
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
03D60: Computability and recursion theory on ordinals, admissible sets, etc.
Related Items
Dot operators, 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
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