Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

"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 :-) )

share|improve this question

closed as off topic by Benjamin Steinberg, Steven Landsburg, Steve Huntsman, Misha, Henry Cohn Mar 24 '13 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.

Did you get as far as the second paragraph of the Wikipedia article on NP? –  Steven Landsburg Mar 24 '13 at 21:09
In general, questions like this are a better fit for mathstackexchange. –  Noah S Mar 24 '13 at 21:22
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. –  Mark Sapir Mar 24 '13 at 21:48
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. –  Mark Sapir Mar 24 '13 at 22:45
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". –  Bruno Mar 25 '13 at 10:16

1 Answer 1

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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.