# NP-complete promise problems? [closed]

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

• 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