2
$\begingroup$

Consider the following decision problem:

Problem 1

INPUT: A graph G.

OUTPUT: YES if G is 3-colorable, NO if not.

This is a well-known NP-complete problem. Now suppose that we have a necessary (but not sufficient) condition for a graph to be 3-colorable, called NC. Consider the following problem:

Problem 2

INPUT: A graph G that satisfies NC.

OUTPUT: YES if G is 3-colorable, NO if not.

Now suppose that it is not known whether NC can be determined in polynomial time. Can we say that Problem 2 is in NP? It seems to me that it should be, seeing as there is a succinct certificate for a YES answer.

(However, I've been told by someone who I trust on other matters that this is a "promise problem" and not in NP, which is why I'm posting it here.)

Update

I'm not entirely happy with the answers below (although the subsequent discussions in the comments were useful), so I will attempt to answer the question myself.

Consider:

Problem 3

INPUT: A planar graph G.

OUTPUT: YES if G is 3-colorable, NO if not.

Now, by the usual definitions, an NP problem is one where, from the set of all binary strings, certain ones (those in the "language") must be recognised. Now, it is not easy to come up with a way to represent planar graphs such that every binary string corresponds to a planar graph. So by convention, Problem 3 means the following:

Given an input string, determine if it represents a planar graph that is 3-colorable.

So by the same convention, Problem 2 defines an NP problem: Given an input string, determine if it represents a graph that satisfies NC that is 3-colorable.

Now, the strings that should give "yes" answers are exactly the same as those that should give "yes" answers to Problem 1. So as NP problems, Problems 1 and 2 are exactly the same. (In other words, the languages they define are the same.)

So to make Problem 2 useful, we need to cast it as a Promise problem, where the input is not all binary strings, but is restricted in some way. Posed in this form, it is not an NP problem.

Improve this question
$\endgroup$
10
  • $\begingroup$ You cannot say that problem $2$ is in NP, because the condition NC might me "is $3$-colorable"! $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Jul 12, 2010 at 16:48
  • $\begingroup$ this is indeed a promise problem. These are common in approximation lower bounds, where you supply a set of inputs that are promised to have either a large or small value for some function, and the problem is to separate them. $\endgroup$
    – Suresh Venkat
    Commented Jul 12, 2010 at 16:50
  • $\begingroup$ or, to satisfy your "(but not sufficient)" let NC be "is $3$-colorable or isomorphic to the complete graph in three vertices". $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Jul 12, 2010 at 16:51
  • $\begingroup$ Mariano: Yes the NC might be that. In this case Problem 2 is trivial, and so in NP. $\endgroup$
    – Emil
    Commented Jul 12, 2010 at 16:51
  • $\begingroup$ Just to clarify, my comment was in respone to Mariano's first comment. $\endgroup$
    – Emil
    Commented Jul 12, 2010 at 16:52

2 Answers 2

Reset to default
1
$\begingroup$

Your Problem 2 is indeed a promise problem. By definition, it is not in NP, because NP is a class of decision problems, not promise problems. But if you like, you can say that it's in a class Promise-NP. See Wikipedia or Oded Goldreich's survey On Promise Problems.

For a decision problem, all strings are either YES instances or NO instances. For a promise problem, some strings are allowed to be "invalid": neither YES nor NO.

In general, if you have a nondeterministic algorithm for a promise problem, then when you feed it inputs that don't satisfy the promise, it will either accept or not — so the the sets of strings accepted and not accepted by your predicate will be supersets of the actual YES and NO instances respectively (and have intersection with the "invalid" instances). In this particular problem, because your condition is a necessary one for 3-colorability, the set of accepted strings will be exactly the set of 3-colorable graphs, but its complement will include graphs that don't satisfy the condition. (If you like, you can artificially change the problem to a decision problem with the same set of YES instances, but then your Problem 2 becomes the same as Problem 1 and therefore in NP.)

Improve this answer
$\endgroup$
14
  • $\begingroup$ Thanks for answering, but you haven't given any specific reason why Problem 2 is not in NP. Would you be able to explain why you think it is not? $\endgroup$
    – Emil
    Commented Jul 12, 2010 at 18:10
  • $\begingroup$ Response to edit: Remember that NC is a necessary condition - in other words, all 3-colorable graphs satisfy NC. For Problem 2, the succinct certificate is an explicit 3-coloring, and this certificate also guarantees that NC is satisfied. (I am not sure the survey paper discusses this situation - could you give me a paragraph reference if it does?) $\endgroup$
    – Emil
    Commented Jul 12, 2010 at 19:01
  • $\begingroup$ I'm still confused by this myself (and sadly, I don't have a postscript reader handy to check out the reference). Wikipedia explicitly says 'There may be inputs which are neither yes or no. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything.' PlanetMath says something similar; it seems like the promise version of a problem can never be more complex than the non-promise version (just ignore the promise!). I'd prefer to say that his problem 2 is surely in NP but not at all guaranteed to be NP-complete. $\endgroup$
    – Steven Stadnicki
    Commented Jul 12, 2010 at 19:30
  • 1
    $\begingroup$ Oh sorry, I didn't realise that your condition is one necessary for 3-colorability. Technically, NP is a class of languages: sets of strings. What is the set of YES instances for your problem 2? It seems the only reasonable definition would be simply the set of 3-colorable graphs, in which case yes, your problem 2 is in NP, because (as a language) it's the same as Problem 1. $\endgroup$
    – shreevatsa
    Commented Jul 12, 2010 at 20:00
  • $\begingroup$ @shreevatsa: could you edit your answer then? $\endgroup$
    – Emil
    Commented Jul 12, 2010 at 20:34
1
$\begingroup$

A promise problem cannot be in NP, just because NP is defined to be a set of languages (or decision problems). It's like asking if the problem "Given n, output 2n" is in P. It's clearly an easy problem, and has a linear time solution, but it cannot be in P as stated because P is a set of decision problems, and the given problem is not a decision problem.

Your problem is in Promise-NP, since it's a promise problem with an efficiently verifiable certificate. See the wikipedia article on promise problems for some more information. Whether NC is a sufficient condition or a necessary condition or a completely arbitrary condition has nothing to do with the problem belonging to Promise-NP. As long as NC is a non-trivial condition which makes this a promise problem, the problem belongs to Promise-NP.

EDIT 1: I thought I should edit this to better answer Emil's question: I just want to know if Problem 2 is in NP. If you think it is not in NP, please could you explain why? It seems to me that "yes" answers do have succinct certificates.

NP is not the set of all things in the universe with succinct certificates! It is the set of all languages that have succinct certificates. Your problem does not define a language. It defines a promise problem. Therefore it cannot be in NP, not because it does not have a short certificate, but because it is not a language at all.

Improve this answer
$\endgroup$
6
  • $\begingroup$ See comments after shreevatsa's answer. $\endgroup$
    – Emil
    Commented Jul 12, 2010 at 20:33
  • $\begingroup$ I answered the comments after Shreevatsa's answer. The fact that NP is defined using decision problems and not promise problems is just a matter of convention. We could equally well have started complexity theory with only promise problems. There is nothing deep here, it's just a matter of convention and definitions. $\endgroup$
    – Rune
    Commented Jul 12, 2010 at 20:57
  • $\begingroup$ I'm not saying there is anything deep here. I just want to know if Problem 2 is in NP. If you think it is not in NP, please could you explain why? It seems to me that "yes" answers do have succinct certificates. $\endgroup$
    – Emil
    Commented Jul 12, 2010 at 21:10
  • 1
    $\begingroup$ I've added an answer to your question in my original answer. How's that? $\endgroup$
    – Rune
    Commented Jul 12, 2010 at 23:16
  • 1
    $\begingroup$ The decision problem associated with a language $L\subseteq$ {0,1}<sup>*</sup> is the following: Given x in L, output yes. Given x not in L (i.e., given x in the complement of L), output NO. If L is the language you claim -- the set of all strings representing graphs that satisfy NC and are 3 colorable, then the complement of L contains all graphs that do not satisfy NC or are not 3-colorable. Thus the output of the algorithm on such graphs will be NO. This is not what you mean by your problem. You want the output to be NO when the graph satisfies NC but is not 3-colorable. $\endgroup$
    – Rune
    Commented Jul 13, 2010 at 3:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .