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?

  • $\begingroup$ 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. $\endgroup$ – lox Jun 30 '19 at 17:42
  • $\begingroup$ 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? $\endgroup$ – user99674 Jun 30 '19 at 18:36
  • $\begingroup$ You are asking for the proof of $\mathsf{NL} \subseteq \mathsf{P}$. $\endgroup$ – Yuval Filmus Jul 1 '19 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy