Your Problem 2 is indeed a promise problem. It By definition, it is not in NP, but 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. (This term doesn't seem very common, though, unlike the other class "Promise-BPP".)See Wikipedia or Oded Goldreich's survey On Promise Problems.The promise classes are different, and sometimes much stronger, than their plain versions. Among other things,
For a problem in the promise version of NP∩co-NP need not be in NP, and (as commented here) there are NP-hard problems in promise-NP∩co-NP while this is not believed to be the case for NP∩co-NP.
Edit (in response to first comment below): Well, because you've constrained your input, so you're no longer working with the same model. In decision problemsproblem, all possible input strings are either YES instances or NO instances, whereas in . For a promise problemsproblem, some strings are allowed to be "invalid": neither YES nor NO.NP is a class of decision problems
In general, in which for all YES instances there is if you have a succinct certificate, and onlynondeterministic algorithm for them. For your Problem 2, although there is a succinct certificate for the YES instancespromise problem, if given an input which does not then when you feed it inputs that don't satisfy the conditionpromise, there may still exist some "certificate" that makes whatever verification you were doing it will either accept or not — so the input. So the sets of strings accepted and rejected not accepted by your predicate will be supersets of the actual YES and NO instances respectively (and have intersection with the "invalid" instances). Sorry if this is unclear; all In this particular problem, because your condition is explained better in a necessary one for 3-colorability, the first few pages set of accepted strings will be exactly the set of 3-colorable graphs, but its complement will include graphs that don't satisfy the survey linked abovecondition. (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.)
