D has polynomial verifyer, the certificate for any word $w \in D$ is at most O(|log w|) space. Prove $D \in P$
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$