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

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

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

• `` Strong NP-Completeness Results
• A comparison of polynomial time reducibilities
• 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?)
• On the complexity of unique solutions
• On the Structure of Polynomial Time Reducibility
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Strong reducibilities
• The polynomial-time hierarchy

Cited in

(25)

• Exotic quantifiers, complexity classes, and complete problems
• On the relative complexity of hard problems for complexity classes without complete problems
• On polynomial-time Turing and many-one completeness in PSPACE
• On 1-truth-table-hard languages
• Strong nondeterministic Turing reduction - a technique for proving intractability
• [[:Publication:1387830|\(R_{1-tt}^Template:\mathcal SN\)(NP) distinguishes robust many-one and Turing completeness]]
• LWPP and WPP are not uniformly gap-definable
• Error-bounded probabilistic computations between MA and AM
• 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 4010508 (Why is no real title available?)
• scientific article; zbMATH DE number 4106271 (Why is no real title available?)
• Complete Problems and Strong Polynomial Reducibilities
• scientific article; zbMATH DE number 1222582 (Why is no real title available?)
• scientific article; zbMATH DE number 1222922 (Why is no real title available?)
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• scientific article; zbMATH DE number 2080215 (Why is no real title available?)
• scientific article; zbMATH DE number 6077 (Why is no real title available?)
• On a criterion of NP-completeness
• Computing and Combinatorics
• On Some $\mathcal{NP}$ -complete SEFE Problems
• Dot operators
• Observations on complete sets between linear time and polynomial time
• On the topological size of p-m-complete degrees
• Comparing reductions to NP-complete sets

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)