7
$\begingroup$

This might be a well-known fact, but I can't convince myself of whether this is true.

Suppose I have some NP language and two different verifying procedures V and V' for L. For any x in L, is it the case that I can always, in polynomial-time, turn a certificate u for x accepted by V into a certificate u' for the same x, accepted by V'?

Or, more concretely, for SAT, is it the case that if someone came up with some verifier that did not rely on satisfying assignments, I could always extract a satisfying assignment from a certificate accepted by that verifier?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ This does not hold in general, assuming $\mathrm{FP\ne TFNP}$. Basically, let $V$ be any verification procedure for any NP-language $L$, and let $V'$ be a verification procedure that expects as a certificate a $V$-certificate stapled together with a solution to an unrelated TFNP problem. $\endgroup$
    – Emil Jeřábek
    Commented Jun 30, 2023 at 14:05
  • $\begingroup$ (The assumption is necessary: “given $x$ and $u$, compute $u'$” is itself a TFNP problem, hence you can always do it in polynomial time if FP = TFNP.) $\endgroup$
    – Emil Jeřábek
    Commented Jun 30, 2023 at 14:10
  • $\begingroup$ True, I see. Thanks! But this doesn't answer the second question, for the particular case of SAT, right? In that case V' is the default verifier expecting a satisfying assignment. Can I always get a satisfying assignment from another certificate? $\endgroup$
    – Noel Arteche
    Commented Jun 30, 2023 at 14:16
  • 1
    $\begingroup$ This is equivalent to the statement that the standard verifier is a p-optimal proof system for SAT. There are reasons to believe this is false, see doi.org/10.1007/3-540-44450-5_29 . $\endgroup$
    – Emil Jeřábek
    Commented Jun 30, 2023 at 14:28
  • $\begingroup$ I see, thanks Emil! This was very helpful. $\endgroup$
    – Noel Arteche
    Commented Jun 30, 2023 at 15:53

1 Answer 1

Reset to default
6
$\begingroup$

For general $L\in\mathrm{NP}$, this is equivalent to $\mathrm{FP=TFNP}$, hence likely false:

On the one hand, if $V$ and $V'$ are verifiers of $L$, then “given $x$ and $u$ such that $V(x,u)$, find $u'$ such that $V'(x,u')$” is a TFNP problem (with the proviso that if $\neg V(x,u)$, any $u'$ is a solution). Thus, such a conversion is possible in polynomial time if $\mathrm{FP=TFNP}$.

On the other hand, given a TFNP problem $S$, let $L=\Sigma^*$, $V$ be its trivial verifier that accepts all certificates, and let $V'$ be a verifier that accepts as a certificate for $x$ a solution of $S(x,y)$. Then a polynomial-time conversion of $V$-certificates to $V'$-certificates solves $S$ in polynomial time.

For the special case where $L$ is SAT and $V'$ its standard verifier, such a conversion exists for all $V$ iff the standard verifier is a p-optimal proof system for SAT (this is just restating the definition using different terminology). There are reasons to believe this is false as well; see

Johannes Köbler and Jochen Messner: Is the standard proof system for SAT p-optimal?, in: Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2000), Lecture Notes in Computer Science vol. 1974, 2000, DOI 10.1007/3-540-44450-5_29.

Improve this answer
$\endgroup$

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.