Promise problems complete for complexity classes
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3858857 (Why is no real title available?)
- scientific article; zbMATH DE number 3811467 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A comparison of polynomial time reducibilities
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
- Comparing complexity classes
- Cryptocomplexity and NP-completeness
- NP is as easy as detecting unique solutions
- Natural Self-Reducible Sets
- On self-reducibility and weak P-selectivity
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Reductions on NP and p-selective sets
- Terminating Turing Machine Computations and the Complexity and/or decidability of Correspondence Problems, Grammars, and Program Schemes
- The complexity of promise problems with applications to public-key cryptography
- The polynomial-time hierarchy
Cited in
(19)- Quantum computing and quadratically signed weight enumerators
- Reductions to graph isomorphism
- scientific article; zbMATH DE number 874695 (Why is no real title available?)
- The complexity of promise problems with applications to public-key cryptography
- Separating complexity classes with tally oracles
- Hard promise problems and nonuniform complexity
- scientific article; zbMATH DE number 18529 (Why is no real title available?)
- Promise problems on probability distributions
- scientific article; zbMATH DE number 761756 (Why is no real title available?)
- Reductions to Graph Isomorphism
- An unambiguous class possessing a complete set
- A common algebraic description for probabilistic and quantum computations
- Do there exist complete sets for promise classes?
- scientific article; zbMATH DE number 1678398 (Why is no real title available?)
- BANISHING ROBUST TURING COMPLETENESS
- scientific article; zbMATH DE number 6515829 (Why is no real title available?)
- Reductions between disjoint NP-pairs
- Restrictive Acceptance Suffices for Equivalence Problems
- Cohesiveness in promise problems
This page was built for publication: Promise problems complete for complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109568)