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

Question

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?

Answer 1

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$