Consider the following decision problem:

Problem 1INPUT: 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 2INPUT: 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 3INPUT: 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.

firstcomment. $\endgroup$ – Emil Jul 12 '10 at 16:52