Promise problems complete for complexity classes

DOI10.1016/0890-5401(88)90030-2zbMath0655.68050OpenAlexW2066390433MaRDI QIDQ1109568

Selman, Alan L.

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

zbMATH Keywords

graph isomorphismpromise problemshardness resultsself-reducible decision problems

Mathematics Subject Classification ID

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