Promise problems complete for complexity classes
From MaRDI portal
Publication:1109568
DOI10.1016/0890-5401(88)90030-2zbMath0655.68050MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
03D15: Complexity of computation (including implicit computational complexity)
Related Items
Reductions to Graph Isomorphism, Reductions to graph isomorphism, Separating complexity classes with tally oracles, Hard promise problems and nonuniform complexity, Quantum computing and quadratically signed weight enumerators, Reductions between disjoint NP-pairs, A common algebraic description for probabilistic and quantum computations
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