Promise problems complete for complexity classes

DOI10.1016/0890-5401(88)90030-2zbMATH Open0655.68050OpenAlexW2066390433MaRDI QIDQ1109568FDOQ1109568

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The polynomial-time hierarchy
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• NP is as easy as detecting unique solutions
• The complexity of promise problems with applications to public-key cryptography
• On self-reducibility and weak P-selectivity
• Title not available (Why is that?)
• A comparison of polynomial time reducibilities
• Comparing complexity classes
• Terminating Turing Machine Computations and the Complexity and/or decidability of Correspondence Problems, Grammars, and Program Schemes
• Cryptocomplexity and NP-completeness
• Reductions on NP and p-selective sets
• Natural Self-Reducible Sets
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• Title not available (Why is that?)

Cited In (19)

• Quantum computing and quadratically signed weight enumerators
• Title not available (Why is that?)
• Reductions to graph isomorphism
• The complexity of promise problems with applications to public-key cryptography
• Separating complexity classes with tally oracles
• Hard promise problems and nonuniform complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Promise problems on probability distributions
• 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?
• Title not available (Why is that?)
• BANISHING ROBUST TURING COMPLETENESS
• Title not available (Why is that?)
• 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)