Equivalence between alternative definitions of NP

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

The definition of $\text{NP}$ in terms of verification can be formally stated as follows:


A language $L$ is in $\text{NP}$ if there exists a polynomial verifier for $L$ such that for every $x$:
$$x \in L \iff \exists u: V(x,u) = 1.$$


Here $u$ serves as a certificate.

To prove that the other definition $\text{NP}$ in terms of NTM implies the one above, you should construct such a polynomial verifier $V$ with the desired property. That is, for every $x \in L$, you need to find a certificate $u$ (you are not given a certificate $u$) such that $V(x,u) = 1$. Note that for every $x \in L$, there is a sequence of nondeterministic choices that makes the NTM $M$ accept $x$. This sequence is the certificate we need. What the polynomial verifier $V$ need to do is just to simulate the action of $M$ using these nondeterministic choices.

StackExchange Computer Science Q#74594, answer score: 6