1
$\begingroup$

I have seen two definitions for the set $NP$. One is that it is the set of languages decidable by a nondeterministic Turing machine (NTM) running in polynomial time, and the other is that it is the set of languages with verifiers that run in polynomial time. Some of my understanding of these definitions have come from 'Aaronson' and 'HarvardLecture'.

I understand that these definitions are equivalent; 'HarvardLecture' and 'Aaronson' provide proofs of the same. If $A$ is the set of languages decidable by an NTM running in polynomial time and $B$ is the set of languages with verifiers that run in polynomial time, their proofs show that $A \implies B$ and $B \implies A$.

Now, I think I understand the $A \implies B$ case, but I'd need some clarification with the $B \implies A$ argument. My reproduction of this argument is the following.

If the language $L$ has a verifier $V$ so that $w \in L \iff V(w,y) = 1$ for some witness $y$, with $V$ being a TM that runs in polynomial time, then an NTM, $M$, in its computation of $w$, can create a computation path for every possible witness, $y'$, and accept $w$ if $V(w,y')=1$ in some path ('Aaronson'). 'HarvardLecture' renders this as guessing the certificate, $y$, for $w$.

But what if the set of every possible witness is $\Sigma^{*}$, a countably infinite set? It seems to me that $M$ must make an infinite number of guesses (and generate infinite paths) to reject some $v \notin L$, and I am not completely sure such an $M$ running in polynomial time can be constructed.

For if our $M$ has a finite number of states then it also has a finite number of transitions, $n$. And if $M$ runs in polynomial time, then all computation paths of $M$ must halt. Finally, if $t$ is the run time of $M$, then all computation paths of $M$ halt within $t$ steps. But even if we were to assume that every transition was possible at every time step and that every path halted after $t$ steps, we would have $n^{t}$ total computation paths of $M$, which is some finite number.

Therefore, $M$ could not generate a computation path for every element of $\Sigma^{*}$ while running in polynomial time.

Unless, of course, I have missed something above.

$\endgroup$

1 Answer 1

0
$\begingroup$

I had been searching for a more formal rendition of the proof beforehand.

Sipser's Introduction to the Theory of Computation contains a more complete version of the argument where you need only to consider strings that have length at most the runtime of the verifier, $V$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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