# NP-complete promise problems? [closed]

Are there any good examples of promise problems that are NP complete?

## closed as too broad by David Richerby, Juho, Evil, cody, Gilles♦Dec 24 '15 at 18:41

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• We don't have a strict policy for list questions, but there is a general dislike. Please note also this and this discussion; you might want to improve your question as to avoid the problems explained there. At minimum the question should identify the criteria for what constitutes an acceptable answer, and it should be possible to produce an acceptable answer that is not too long (no more than a few paragraphs long). – D.W. Dec 10 '15 at 6:09

2. Yes. If you want to say informally that something is NP-complete (usually meaning "there's an obvious equivalent decision problem that is NP-complete"), then you can reformulate any decision problem as a promise problem just by taking the promise to be the set of sensible inputs. For example we can make a promise version of Dominating Set by taking the promise $L_{YES} \cup L_{NO}$ to be the set of all simple, undirected, unweighted graphs (so if you give it an input that's not a graph, it doesn't have to do anything in particular).
• @ABD. Yes, (Halting problem is decidable) $\Rightarrow$ (P = NP). We'd also have (Halting problem is decidable) $\Rightarrow$ (Moon is made of green cheese). – Rick Decker Dec 10 '15 at 16:26