# How is the NP verifier polynomial?

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.

You run your NTM, and at any point where it could decide between n > 1 actions, it picks an action k and writes k to a tape.

Now you build a TM. It’s identical to the NTM, except at every point where the NTM made a decision, your TM reads a number k from the NTMs successful run, and takes action #k. That’s it.

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.

• 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.
– wff
Jun 6, 2020 at 10:03
• @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. Jun 6, 2020 at 11:20
• 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. Jun 6, 2020 at 11:27