Conversely, if a problem is nondeterministically polynomial-time decidable, then we can think of the witness w as telling us which choice to make each time we need to make a choice in the nondeterministic procedure, and then the right witness will lead us to accept. In this way, we have a dual conception of the class NP, either as the result of nondeterminism or by means of the concept of verification.
