@shreevasta: Well, your last paragraph now is quite muddled. If you don't believe Problem 2 to be in NP, then please explain why not. Bear in mind that NC is a necessary condition, so the set of "yes" answers for Problem 2 is the same as that for Problem 1.

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.

@Antonio: No, we do not know if determining NC is in NP. I'm not sure that trusting the promise is an issue, because NC is a necessary condition.

@shreevatsa: could you edit your answer then?

See comments after shreevatsa's answer.

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

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?

Just to clarify, my comment was in respone to Mariano's first comment.

Mariano: Yes the NC might be that. In this case Problem 2 is trivial, and so in NP.

All trees on $n$ vertices have the same Tutte polynomial, so it's not that. Are you just asking for a canonical labelling?

Surely "not solvable in polynomial time" should be "not known to be solvable in polynomial time".

The URL didn't work for me until I added "www."

Similar problems are #P-complete, for example counting the number of induced subgraphs with m edges in a bipartite graph. (A reduction from 1-in-3 monotone 3-SAT springs to mind.) However, the result by Ehrenfeucht & Karpinksi suggests that there could be an efficient algorithm.

I want a video!

There should be 3 colors, for the 3 orientations. (I think it even says this in the book.) I think the gray is a mistake introduced by the cover designer - unless there is some hidden meaning in the arrangement of gray rhombi?

I believe John Nash put unsolved problems in his exams, because he thought that if the students did not realize how hard they were, they might actually be able to solve them!