2
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Nov 25, 2020 at 20:23
  • $\begingroup$ @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) $\endgroup$
    – DeeDee
    Commented Nov 25, 2020 at 20:25
  • $\begingroup$ No, there aren't: there are only $2^{\text{poly}(|w|)}$, which is finite. $\endgroup$
    – D.W.
    Commented Nov 25, 2020 at 20:26
  • $\begingroup$ @D.W. oh really? So you can brute force check all possible certificates. made the approriate update to question $\endgroup$
    – DeeDee
    Commented Nov 25, 2020 at 20:26
  • 1
    $\begingroup$ Perhaps you can write an answer to your own question now? $\endgroup$
    – D.W.
    Commented Nov 25, 2020 at 20:27

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.