1
$\begingroup$

Can you build a solver from a verifier?

I see that if you start with an NP-verifier TM the answer is yes, you can build a solver TM. How about for circuits? Can you go from a circuit that implements a verifier for instances of size n that is of size polynomial in n to a circuit that implements a solver for instances of size n?

$\endgroup$
3
  • $\begingroup$ In principle I see nothing preventing you from designing a circuit that 1) explicitly generates all $2^n$ binary inputs $B_1,B_2$, each with $n$ lines, 2) feeds each $B_i$ into a copy of the verifier circuit to compute an output $x_i$, 3) feeds the $2^n$ outputs $x_1,x_2,\dots$ of the verifiers into a small sub-circuit with $2^n$ outputs $y_1,y_2,\dots$ such that $y_i$ is true iff $x_i$ is true and $x_1,\dots,x_{i-1}$ are false, 4) ANDs each line of each binary input $B_i$ with $x_i$ to obtain $C_i$, 5) For each $j$, ORs together the $j$-th line of all $C_i$s to compute the $j$-th output $\endgroup$
    – Steven
    Dec 1 '20 at 16:10
  • $\begingroup$ If the second circuit's size is limited to being polynomial to n, you're basically asking whether P = NP, since CIRCUIT-VALUE is in P. $\endgroup$
    – Kyle Jones
    Dec 1 '20 at 19:33
  • $\begingroup$ @KyleJones yes not asking that -- put no limit on solver size, any size is fine--just wondering if the information is in one to get the other $\endgroup$
    – user129081
    Dec 1 '20 at 19:37

Your Answer

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