"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 :-) )
closed as off topic by Benjamin Steinberg, Steven Landsburg, Steve Huntsman, Misha, Henry Cohn Mar 24 at 22:20
Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.
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.