definition of NP "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 :-) )
 A: 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.  
