A note on complete problems for complexity classes
From MaRDI portal
Recommendations
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)