1
$\begingroup$

I've revisited trying to understand the proof to why NTM exists iff there is a verifier. I think I'm finally understanding the proof but I want to make sure and thus have some questions as follow up along with to check if I'm understanding.

  1. For the forward implication (there exists a verifier $V$ and we want to show this implies the existence of an NTM $N$), we can, according to Sipser, "Nondeterministically select string $c$ of length at most $n^k$. Then we run $V$ on input $(w,c)$ and accept if $V$ accepts, otherwise reject." I'm wondering if $V$ would be run as part of the algorithm on each branch of $N$. In other words, for any node in the computation tree of $N$, the verifier will be run on the that current string, and the branch will produce a YES answer only if the verifier accepts that string. Am I understanding this correctly? So it would run concurrently, and since the verifier runs in $O(n^k)$ and the NTM runs in $O(n^q)$, then this still runs in polynomial time if the verifier is run at every step in the computation.

  2. For the backward implication, we assume $A$ is decided by a polynomial time NTM and construct a polynomial time verifier $V$. When we say that $A$ "is decided by" $N$, does this mean that $N$ is correctly able to determine if any given branch of computation results in accept or reject? This feels a bit cyclic to me, since we are trying to construct the verifier $V$ given $N$. I don't see how $N$ could decide $A$ without $N$ having a verifier constructed already. In other words, without a verifier, how would the NTM know if it should accept/reject on any of its given branches?

$\endgroup$
3
$\begingroup$
  1. Essentially, yes. Though I usually find it easier to think of nondeterministic machines as guessing what to do. So, as the machine runs, it starts by repeatedly doing the following: either it guesses that the current string is good, and verifies it, or it guesses what the next character should be, and it repeats. Thus, if there's some string that the verifier will accept, some sequence of guesses will lead to the machine producing that exact string and then deciding to verify it, so the machine will accept. (Also, the machine needs to keep track of how long the string is, so it can stop if it gets too long.)

  2. We have a nondeterministic Turing machine $N$ and the guesses it makes lead it down some path of the tree of possible computations. If that path ends in an accepting state, the machine is defined to accept its input; if no path ends in an accepting state, it is defined to reject. There's no circularity: that's just the definition of what it means for a nondeterministic machine to accept or reject.

    From this machine, we build a verifier. The input to the verifier is a description of a computation path, and the verifier checks that each action taken on that path is a thing that $N$ could do in that state, and that the path ends in an accepting state. If those conditions are met, the verifier has verified that $N$ really would accept the given input.

$\endgroup$
  • $\begingroup$ Thank you! This does help. I suppose I’m just a bit confused on how the NTM by definition, in question 2, is able to check if some path ends in an accepting state. In order to check if the path ends in an accepting state, doesn’t the NTM need some verifier to be able to do this? From my understanding, a verifier by definition takes in as input a certificate and will verify if it will accept or reject. So doesn’t the NTM by definition need a verifier to know whether to accept or reject? In other words, without a verifier existing, how could it know if it should accept or reject? $\endgroup$ – rb612 Apr 14 '18 at 18:50
  • $\begingroup$ No. At any time, the NTM knows what state it's in, and it knows which state is accepting. So, if it reaches the accepting state, it knows it's there, and it halts and accepts by definition. It doesn't need to check anything, except what state it's in at the moment. $\endgroup$ – David Richerby Apr 14 '18 at 18:52
  • $\begingroup$ Ah, so then is the point of creating a verifier from this NTM to be able to check some arbitrary certificate? And if so, then why do we need a verifier to create an NTM (the forward implication) if it's already built-in? $\endgroup$ – rb612 Apr 14 '18 at 18:57
  • 1
    $\begingroup$ The point is to show that NP can be defined in two different ways: it's the class of languages that are accepted by NTMs in polynomial time, and also the class of languages where solutions can be verified by DTMs in polynomial time. The fact that the same languages can be defined in two different ways like that (and, in fact, in many other ways, too, some of which have nothing to do with TMs) tells us that NP is important in its own right, rather than just being an artifact of the definition we chose for Turing machines. $\endgroup$ – David Richerby Apr 14 '18 at 20:23
  • 1
    $\begingroup$ Not necessarily. Consider, for example, 3-SAT. Suppose we have a formula $\phi$ and I tell you that, according to my nondeterministic Turing machine, $S$ is a satisfying assignment to that formula. You can verify that claim just by checking that it makes the formula true. You certainly don't need to know the details of my Turing machine or even believe that I really have a nondeterministic Turing machine in my office. There is a verifier based on the definition of the TM but there can be other verifiers, too. $\endgroup$ – David Richerby Apr 15 '18 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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