# 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.

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.