"Popular" discussions of PvsNP often begin by characterizing NP problems as those for which a purported solution can be verified in polynomial "time". Later the definition changes to; the problem is solvable by a non-deterministic Turing machine in polynomial time. It's not obvious to me that these are equivalent definitions. Is there a simple demonsration of this point. (I want more than just a yes or no answer :-) )
9
-
4$\begingroup$ Did you get as far as the second paragraph of the Wikipedia article on NP? $\endgroup$– Steven LandsburgCommented Mar 24, 2013 at 21:09
-
$\begingroup$ In general, questions like this are a better fit for mathstackexchange. $\endgroup$– Noah SchweberCommented Mar 24, 2013 at 21:22
-
$\begingroup$ In defense of the question. It is indeed a basic and easy fact, but I do not know a CS text where it is fully explained. For example, the text in Wiki uses a word "guess" which is a valid CS slang but for a non-CS person, it is not clear how a Turing machine can "guess" anything. $\endgroup$– user6976Commented Mar 24, 2013 at 21:48
-
1$\begingroup$ Looked at Section 2.1.2 of Arora and Barak. The explanation there is not precise enough (at least not to my taste). For example, what does it mean "then the machine will run another machine"? How a TM can run another TM? It is not a critique of the book. The target readers probably would "eat" that explanation without a problem. The problem starts when you try to apply it in an algebraic setting (say when you try to simulate the machine in a group). Then you actually need a much more precise definition of the machine. $\endgroup$– user6976Commented Mar 24, 2013 at 22:45
-
1$\begingroup$ Mark, you should'nt skip Chapter 1! There, it is clearly and formally defined what a machine is, and what it means for a machine to "run another one". $\endgroup$– BrunoCommented Mar 25, 2013 at 10:16
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
Yes, the proof is not difficult. Suppose that a problem has proofs verified in polynomial time by a deterministic Turing machine $M$. That means that $M$ has two special tapes: the INPUT tape, and a PROOF tape. Given an input word $u$ written on the INPUT tape and a text written on the PROOF tape, $M$ checks in time polynomial in $|u|$ if the proof proves that the word should be accepted. Now consider a new non-deterministic Turing machine $M'$ with the same tapes as $M$. First $M'$ writes a text on the PROOF tape (non-deterministically) using the PROOF tape alphabet of $M$. Then (again at non-predetermined time) $M'$ turns on $M$ to check if the text written on the PROOF tape is a valid proof. Conversely, suppose that there exists a non-deterministic Turing machine $M$ which checks if a word $u$ should be accepted. Then the "proof" is the accepting computation of $M$. Clearly, given a sequence of commands of $M$ of length $O(|u|^k)$, it would take at most $O(|u|^k)$ steps by a deterministic Turing machine to check if $M$ accepts $u$ using this sequence of commands.