I'm having some problems in understanding the two alternative definitions of NP. They're presented as equivalent, but to me they seem to define different class of problems. Intuitively, we can think of a non-deterministic TM as branching at every step to check all possible alternatives in parallel. Also, we can see it as guessing the right next state at every stage of the computation. In both cases, if there is a computation path which terminates in an accepting state, the TM is said to accept its input, otherwise it rejects it. On an informal level, we can define NP in two ways.
- The class of problems solvable in polynomial time by a NTM. That is, given an instance $x$ of the problem, there is a NTM $M$ which accepts $x$.
- The class of problems which can be verified in polynomial time by a TM. In this case, together with the input we get a certificate which provides a proof that $x$ is a solution. We can then check if this is the case by some polynomial time procedure.
Now, what baffles me is that taking the first definition, it would seem as if a NTM would always find the accepting computation path and will thus always be able to accept its input (provided this is in the language recognized by the TM). On the other hand, by the second definition, since we're given only one certificate, $x$ could actually be in the language recognized by $M$, but we cannot tell because we've been given the wrong certificate.
On a second thought, the problem here could be that I'm thinking as a NTM as actually performing a computation, while it is just a theoretical construct. That is, even if we allow the TM to accept if at least one computation path accepts, no one guarantees that a concrete run of the algorithm will "follow" this computation path. So, in this sense we could see the equivalence by stating that, in the case of a verifier, the TM accept if there is at least one certificate which proves that the input is in the language recognized by the TM; this parallels the way in which a NTM needs only to have at least one computation path which accepts the input.
Any deeper insight or also formal derivations would be very appreciated.