Equivalence between alternative definitions of NP

Question

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.

1. 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$.
2. 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.

Answer 1

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.

Answer 2

This is an informal version of the answer you require I guess.

In this case both(TM and NTM), what they do is verification only. Assume that we have a problem like Sudoku which can be verified on a TM in polynomial time. We are asked to solved that so we can try to brute-force all possible solutions as a worst method to solve.

In a normal CPU you can make loop which checks for a solution in the solution space. But if you have as many number of CPUs as you want working in parallel then you can verify all the possible solutions by the time of a single verification. It is only one difference & that is TM traverse in solution space one after another and NTM traverse all at once.

Theoretically NTM doesn't choose the correct path always. It has non-determinism so it goes on all path at the same time. While processing any input if one of the state you are in is an accepting state then NTM accepts that input.

Answer 3

A non-deterministic turing machine can only find an accepting path if there is one. For example, if you try to solve the Travelling Salesman problem, and you have a configuration where the shortest tour takes 1,272 miles, and you ask if there is a tour taking 1,271 miles or less, then the NTM isn't going to end up in an accepting state.

The easier way to see the equivalence is by using the model that an NTM just magically picks the correct decision at every step where it is allowed to choose. Now in one direction, let an NTM find an accepting path, record all the magically correct decisions, and call that sequence of decisions a "certificate". Now you build a deterministic TM exactly like the NTM, except that where the NTM made a magically correct decision, the deterministic TM consults the next bit of the "certificate" to decide. Obviously the NTM and the DTM make exactly the same decision at every step, so the DTM will also find an accepting state.

The other direction is even easier: Build a TM that takes a problem and a certificate as its input, and which finds an accepting state with the right certificate. Then you can build a NTM by letting it choose which decision to make at every point where the DTM consulted the certificate to make a decision. To find an accepting state, all the NTM has to do is magically guess the decision that the TM would have made based on the certificate.