0
$\begingroup$

If we start with the definition of L being in NP if "there exists a polynomial NTM that decides L" (where polynomial for an NTM means the length of the worst run as a function of the size/length of the input / the maximal tree depth)

There is a proof that L is in NP iff there exists a polynomial TM verifier for L. Regarding the "L is in NP" -> "there exists a polynomial TM verifier for L" side: Let N be that NTM I fail to understand how given (w, R) where R is the encoding for an accepting run of N on w, we can verify this in polynomial time in regards to w (as this is how the time complexity for a Verifier is defined)

We can show R's length is polynomial in w, but how would we verify that it is a valid run for N in polynomial time? We need to verify every 2 consecutive configurations in R are valid, but since for NTM's the transition function maps to a set of (Q x Gamma x {L,R}) possibilities - I can't figure out how this is possible.

Update:

Let me clarify a little further. An obviously bad (non polynomial) solution would be to have the verifier initially write the whole encoding on N on its tape, and then "search through it" to see if a transition is valid. But since the encoding of N is certainly not necessarily polynomial in N, this doesn't work.

It seems the answer has to rely on having the "inner workings" of N "embedded" in the verifier therefore avoiding time complexity issue as we are avoiding time complexity issues by having things "embedded" - but I fail to see how that could then be used further. I see how this opens an avenue of possibility, but can't see it through. I'm assuming there is some low-level technical grunt work so that the right transitions can be "embedded" straight into the verifier.

$\endgroup$
0
$\begingroup$

We need to verify every 2 consecutive configurations in R are valid, but since for NTM's the transition function maps to a set of (Q x Gamma x {L,R}) possibilities - I can't figure out how this is possible.

The size of the set of possibilities $Q \times \Gamma\times \{L,R\}$ is constant. By definition, a NTM has a constant size set of states $Q$, a constant size alphabet $\Gamma$, and the size of the set $\{L,R\}$ is $2$. Besides, to verify that a transition is valid we do not need to consider all possible transistions, we only need to check that the single given transition is valid.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Absolutely. The issue is this constant size is not necessarily polynomial in regards to the input. If we want to verify config1->config2 is valid, we can't "magically" see that it is valid.. or can we? :) Per my update, I vaguely see how it might be possible if this can somehow be embedded within the verifier itself. $\endgroup$ – wff Jun 6 at 10:03
  • $\begingroup$ @wff You are overthinking this. Anything that is constant is polynomial. The verifying DTM does not need to write the encoding of N onto its tape at all or search through it. The verifying DTM will simply have the allowable transitions of the original NTM encoded into its transition table. $\endgroup$ – Tom van der Zanden Jun 6 at 11:20
  • $\begingroup$ On a high level, the verifier DTM will simply encode the information about the previously read state description (which is just the state of the NTM plus the character under the head) from the transcript into its own state. When it reads the next state from the transcript, the transition table of the DTM tells it whether what the NTM did was valid or not. It does not need to look anything up. $\endgroup$ – Tom van der Zanden Jun 6 at 11:27

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.