# Can you build a solver from a verifier?

Given code to just an NP-verifier, where the certificate/witness is required to be of size polynomial in the instance, for a language L, can you, from that data alone, construct code for a solver, or generate / get back the language L itself?

At a glance, the answer seems to be yes--you could just try every word, certificate pair; however, there is a part I'm not sure about with this process: sure there are only a finite number of words of each size, but there are an infinte number of words that are poly|w| for any given size |w| that are potential certificates. So, without the certificates, you could be trying different strings as the second input for the same word as first input forever to no avail.

Thanks!

• Please define what kind of verifier you are talking about. A NP-verifier, where the certificate/witness is required to be of size polynomial in the instance? An arbitrary verifier? Why do you think there are an infinite number of words that are of size $|w|$? It seems there are obviously exactly $2^{|w|}$, assuming a binary alphabet.
– D.W.
Nov 25 '20 at 20:23
• @D.W. there are a finite number of words of size |w| but there are an infinte number of words of size poly|w| (infinite number of potential certificates for any word of any given size) Nov 25 '20 at 20:25
• No, there aren't: there are only $2^{\text{poly}(|w|)}$, which is finite.
– D.W.
Nov 25 '20 at 20:26
• @D.W. oh really? So you can brute force check all possible certificates. made the approriate update to question Nov 25 '20 at 20:26
• Perhaps you can write an answer to your own question now?
– D.W.
Nov 25 '20 at 20:27

Having a verifier for a language in general is known as semidecidability, which is actually weaker than decidability. So in general, the answer is no, we can't build a decider for $$L$$.
But if the verifier is efficient (i.e., $$L \in$$ NP), then indeed $$L$$ is decidable, and your argument is pretty close for why that is.
Let's say we have an efficient verifier $$V(x,c)$$.
Given an $$x \in \Sigma^*$$, the "certificate space" is $$C=\{c \in \Sigma^* \mid |c| \leq p_L(|x|)\}$$, where $$p_L$$ is a polynomial. That means the certificate space is actually finite. $$x \in L$$ if and only if there exists a $$c \in C$$ such that $$V(x,c)$$ accepts. So indeed we can just check every possible certificate for a given input $$x$$ to construct a decider for $$L$$.
In fact with a bit more work you can show that $$L \in$$ EXP, meaning $$L$$ is decidable in exponential time.