Promise problems complete for complexity classes

DOI10.1016/0890-5401(88)90030-2zbMath0655.68050MaRDI 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 isomorphism; promise problems; hardness results; self-reducible decision problems

Mathematics Subject Classification ID

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, 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