Promise problems complete for complexity classes

DOI10.1016/0890-5401(88)90030-2MaRDI QIDQ1109568zbMATH OpenOpenAlexFDO

Authors Alan L. Selman

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)

Recommendations

• scientific article; zbMATH DE number 18529
• Do there exist complete sets for promise classes?
• The complexity of promise problems with applications to public-key cryptography
• scientific article; zbMATH DE number 874695
• Optimal proof systems imply complete sets for promise classes

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)