# D has polynomial verifyer, the certificate for any word $w \in D$ is at most O(|log w|) space. Prove $D \in P$

Given that a language D has a polynomial verifier,

and given that for every word $$w \in D$$, the length of the certificate $$c$$ is $$O(\log|w|)$$ space.

How can I prove that $$D\in P$$ ?

My idea was to create a TM that takes a word w and runs the verifier on all the strings that are potentially a certificate but I don't know how to claim that such a machine will stop? How can I limit the number of certificates my machine will generate?

• You're on the right track. If the certificate is in length $O(\log n)$, then the number of possible certificates is $2^{O(\log n)}$. I'm assuming the certificate can be tested in polynomial time.
– lox
Jun 30, 2019 at 17:42
• Yes it does verify in polynomial time, but can you please explain in a bit more details why is this the number of possible certificates?
– user99674
Jun 30, 2019 at 18:36
• You are asking for the proof of $\mathsf{NL} \subseteq \mathsf{P}$. Jul 1, 2019 at 16:35

Suppose language $$D \in NP$$ and for every input $$w \in D$$, the certificate $$y_w$$ is of logarithmic length; $$|y_w| = O(\log|w|)$$, and a polynomial verifier $$V(w,y)$$ exists for $$D$$.

We can also say: a constant $$c$$ exists s.t for any $$w \in D$$ whose certificate is $$y_w$$, $$|y_w| \leq c \log |w|$$

Consider the following algorithm $$A$$:

Given input $$x$$, for every possible certificate $$y_i$$ of length at most $$c \log |x|$$, run $$V(x,y_i)$$

$$\bullet$$ If $$V(x,y_i) = 1$$, then $$x$$ has a provable witness and $$x \in D$$

$$\bullet$$ If $$V(x,y_i) = 0$$, continue to the next certificate. If all certificates are exhausted, then no $$y_x$$ exists, and $$x \notin D$$.

$$A$$ checks at most $$2^{c \log |x|}$$ certificates, and $$2^{c \log |x|} = |x|^c$$. $$V$$ verifies each certificate at polynomial time (say $$|x|^k$$), so in total $$A$$ runs in $$O(|x|^{k+c})$$ which is polynomial in $$|x|$$

We get that $$D$$ can be decided in polynomial time $$\Rightarrow D \in P$$