Promise problems complete for complexity classes
From MaRDI portal
Publication:1109568
DOI10.1016/0890-5401(88)90030-2zbMath0655.68050OpenAlexW2066390433MaRDI QIDQ1109568
Publication date: 1988
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(88)90030-2
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (8)
Reductions between disjoint NP-pairs ⋮ Promise Problems on Probability Distributions ⋮ Separating complexity classes with tally oracles ⋮ Reductions to graph isomorphism ⋮ Reductions to Graph Isomorphism ⋮ Hard promise problems and nonuniform complexity ⋮ A common algebraic description for probabilistic and quantum computations ⋮ Quantum computing and quadratically signed weight enumerators
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On self-reducibility and weak P-selectivity
- NP is as easy as detecting unique solutions
- Reductions on NP and p-selective sets
- A comparison of polynomial time reducibilities
- Comparing complexity classes
- The polynomial-time hierarchy
- The complexity of promise problems with applications to public-key cryptography
- Terminating Turing Machine Computations and the Complexity and/or decidability of Correspondence Problems, Grammars, and Program Schemes
- Natural Self-Reducible Sets
- Cryptocomplexity and NP-completeness
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
This page was built for publication: Promise problems complete for complexity classes