<p>For general <span class="math-container">$L\in\mathrm{NP}$</span>, this is equivalent to <span class="math-container">$\mathrm{FP=TFNP}$</span>, hence likely false:</p>
<p>On the one hand, if <span class="math-container">$V$</span> and <span class="math-container">$V'$</span> are verifiers of <span class="math-container">$L$</span>, then “given <span class="math-container">$x$</span> and <span class="math-container">$u$</span> such that <span class="math-container">$V(x,u)$</span>, find <span class="math-container">$u'$</span> such that <span class="math-container">$V'(x,u')$</span>” is a TFNP problem (with the proviso that if <span class="math-container">$\neg V(x,u)$</span>, any <span class="math-container">$u'$</span> is a solution). Thus, such a conversion is possible in polynomial time if <span class="math-container">$\mathrm{FP=TFNP}$</span>.</p>
<p>On the other hand, given a TFNP problem <span class="math-container">$S$</span>, let <span class="math-container">$L=\Sigma^*$</span>, <span class="math-container">$V$</span> be its trivial verifier that accepts all certificates, and let <span class="math-container">$V'$</span> be a verifier that accepts as a certificate for <span class="math-container">$x$</span> a solution of <span class="math-container">$S(x,y)$</span>. Then a polynomial-time conversion of <span class="math-container">$V$</span>-certificates to <span class="math-container">$V'$</span>-certificates solves <span class="math-container">$S$</span> in polynomial time.</p>
<p>For the special case where <span class="math-container">$L$</span> is SAT and <span class="math-container">$V'$</span> its standard verifier, such a conversion exists for all <span class="math-container">$V$</span> 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</p>
<p>Johannes Köbler and Jochen Messner: <em>Is the standard proof system for SAT p-optimal?</em>, in: Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2000), Lecture Notes in Computer Science vol. 1974, 2000, DOI
<a href="https://doi.org/10.1007/3-540-44450-5_29" rel="noreferrer">10.1007/3-540-44450-5_29</a>.</p>

CC BY-SA 4.0
2023-06-30T16:14:44.177Z
2023-06-30T16:14:44.177Z
Emil Jeřábek
<p>This might be a well-known fact, but I can't convince myself of whether this is true.</p>
<p>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'?</p>
<p>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?</p>

CC BY-SA 4.0
2023-06-30T14:05:55.623Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-06-30T14:10:30.363Z
(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.)
Emil Jeřábek
CC BY-SA 4.0
2023-06-30T14:16:29.990Z
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?
Noel Arteche
CC BY-SA 4.0
2023-06-30T14:28:27.430Z
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 https://doi.org/10.1007/3-540-44450-5_29 .
Emil Jeřábek
CC BY-SA 4.0
2023-06-30T15:53:52.387Z
I see, thanks Emil! This was very helpful.
Noel Arteche
CC BY-SA 4.0
2023-06-30T15:56:48.130Z
Write an answer @EmilJeřábek!
cody
<sat><np><proofs>
Conversion between NP certificates
Noel Arteche
# Conversion between NP certificates

(Asked by: username_0 on 2023-06-30)

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?

**Tags:** sat, np, proofs
> **Comments:**
> **username_1**: 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.  
> **username_1**: (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.)  
> **username_0**: 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?  
> **username_1**: 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 https://doi.org/10.1007/3-540-44450-5_29 .  
> **username_0**: I see, thanks Emil! This was very helpful.  
> **username_2**: Write an answer @EmilJeřábek!  

---

## 1 answers

### Answer by username_1 on 2023-06-30. Score: 6 | Accepted answer

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](https://doi.org/10.1007/3-540-44450-5_29).


---

