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

  • 1
    $\begingroup$ 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). $\endgroup$
    – D.W.
    Dec 10 '15 at 6:09

There's two trivial answers:

  1. No. For a problem to be NP-complete it must be in NP. To be in NP it must be a decision problem and promise problems aren't decision problems (they don't have to answer Yes or No on inputs outside the promise).

  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).

So there's no list of NP-complete promise problems because either none of them are (the strict answer), or you can just take any NP-complete problem and make a promise version.

  • $\begingroup$ ( For a problem to be NP-complete it must be in NP. To be in NP it must be a decision problem) So, if we solved the halting problem, then we proved that P=NP ? If so, is there an offical paper or source that states so ? $\endgroup$
    – ABD
    Dec 10 '15 at 14:21
  • 1
    $\begingroup$ @ABD. Yes, (Halting problem is decidable) $\Rightarrow$ (P = NP). We'd also have (Halting problem is decidable) $\Rightarrow$ (Moon is made of green cheese). $\endgroup$ Dec 10 '15 at 16:26
  • $\begingroup$ All you have to do is to build a model of computation that can simulate a TM => a Universal TM (UTM), then by using a specific encoding scheme, you can halt any input. $\endgroup$
    – ABD
    Dec 10 '15 at 20:15
  • $\begingroup$ @ABD, the Halting Problem isn't simply to halt on any input, it's a problem where we get the description of a Turing machine and a string and we have to decide whether the given TM halts on the given string. It's provably undecidable, so "solving" it would be a contradiction, and and thus you could derive any result from it (including both P = NP and P != NP). $\endgroup$ Dec 11 '15 at 0:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.