MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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.

1

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.