A note on complete problems for complexity classes

DOI10.1016/0020-0190(86)90078-5MaRDI QIDQ1097029zbMATH OpenOpenAlexFDO

Authors Klaus Ambos-Spies

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) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 6077
• Complete Problems and Strong Polynomial Reducibilities
• On the relative complexity of hard problems for complexity classes without complete problems
• scientific article; zbMATH DE number 4106271
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP

Cites work

• scientific article; zbMATH DE number 3814972 (Why is no real title available?)
• scientific article; zbMATH DE number 3921977 (Why is no real title available?)
• scientific article; zbMATH DE number 3922634 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• On the Structure of Polynomial Time Reducibility
• On the complexity of unique solutions
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Strong reducibilities
• The polynomial-time hierarchy
• `` Strong NP-Completeness Results

Cited in

(20)

• On the relative complexity of hard problems for complexity classes without complete problems
• Comparing reductions to NP-complete sets
• On 1-truth-table-hard languages
• Observations on complete sets between linear time and polynomial time
• On polynomial-time Turing and many-one completeness in PSPACE
• On a criterion of NP-completeness
• scientific article; zbMATH DE number 3922634 (Why is no real title available?)
• scientific article; zbMATH DE number 4010508 (Why is no real title available?)
• Computing and Combinatorics
• Exotic quantifiers, complexity classes, and complete problems
• LWPP and WPP are not uniformly gap-definable
• Complete Problems and Strong Polynomial Reducibilities
• scientific article; zbMATH DE number 4106271 (Why is no real title available?)
• scientific article; zbMATH DE number 3921977 (Why is no real title available?)
• Dot operators
• scientific article; zbMATH DE number 2080215 (Why is no real title available?)
• Error-bounded probabilistic computations between MA and AM
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• Strong nondeterministic Turing reduction - a technique for proving intractability
• On Some $\mathcal{NP}$ -complete SEFE Problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1097029)