Decision problem restricted to inputs that satisfy some necessary condition. - MathOverflow

Decision problem restricted to inputs that satisfy some necessary condition.

2010-07-12T16:44:19Z

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.

Answer by shreevatsa for Decision problem restricted to inputs that satisfy some necessary condition.

2010-07-12T17:57:13Z

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

Answer by Rune for Decision problem restricted to inputs that satisfy some necessary condition.

2010-07-12T20:14:47Z

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.