<p>This essentially stems from the fact that satisfying assignments of the produced formula encode accepting computation paths of the nondeterministic TM for the problem that we started with. As may assume that this NTM works by first &quot;guessing&quot; a certificate nondeterministically and then verifying it using a deterministic procedure, which allows us to &quot;read off&quot; the original certificate from a satisfying assignment.</p>

CC BY-SA 4.0
2023-04-01T21:48:38.793Z
2023-04-01T21:48:38.793Z
Watercrystal
<p>The book by Wigderson includes this quote on page 39, following the statement of the Cook-Levin theorem that <span class="math-container">$SAT$</span> is <span class="math-container">$\mathsf{NP}$</span>-complete:</p>
<blockquote>
<p>The proof of this theorem (namely, the construction of the reduction
algorithm <span class="math-container">$f$</span> ) gives an extra bonus that turns out to be extremely
useful: It maps witnesses to witnesses. More precisely, for any
witness <span class="math-container">$y$</span> certifying that <span class="math-container">$z \in C$</span> (via some verifier <span class="math-container">$VC$</span> ), the same
reduction <span class="math-container">$f$</span> converts the witness <span class="math-container">$y$</span> to a Boolean assignment of the
variables of the formula <span class="math-container">$f(z)$</span> that satisfy it. In other words, this
reduction translates not only between the decision problems, but also
between the associated search problems.</p>
</blockquote>
<p>The Arora-Barak book makes a similar remark, on page 50 under &quot;More Thoughts on the Cook-Levin Theorem&quot;:</p>
<blockquote>
<p>The reduction <span class="math-container">$f$</span> from an <span class="math-container">$\mathsf{NP}$</span>-language <span class="math-container">$L$</span> to <span class="math-container">$SAT$</span> presented in Lemma 2.11
not only satisfied that <span class="math-container">$x \in L \iff f(x) \in SAT$</span> but actually the proof
yields an efficient way to transform a certificate for <span class="math-container">$x$</span> to a
satisfying assignment for <span class="math-container">$f(x)$</span> and vice versa. We call a reduction
with this property a Levin reduction. One can also modify the proof
slightly (see Exercise 2.13) so that it actually supplies us with a
one-to-one and onto map between the set of certificates for <span class="math-container">$x$</span> and the
set of satisfying assignments for <span class="math-container">$f(x)$</span>, implying that they are of the
same size.</p>
</blockquote>
<p>There are other references to this fact of the Cook-Levin theorem. Recall that the proof of the Cook-Levin theorem takes a computation history of a Turing machine, a polytime verifier, and produces a polysized CNF formula which is satisfiable if and only if the verifier accepted.</p>
<p>I do not see how the Cook-Levin theorem implies this transformation from witnesses to witnesses, as it does from problems to problems. I would appreciate any directions or pointers, I feel like I may be missing something obvious.</p>

<cook-levin>
Cook-Levin Theorem implies a transformation from witnesses to witnesses
abrahimladha
# Cook-Levin Theorem implies a transformation from witnesses to witnesses

(Asked by: username_0 on 2023-04-01)

The book by Wigderson includes this quote on page 39, following the statement of the Cook-Levin theorem that $SAT$ is $\mathsf{NP}$-complete:

> The proof of this theorem (namely, the construction of the reduction
> algorithm $f$ ) gives an extra bonus that turns out to be extremely
> useful: It maps witnesses to witnesses. More precisely, for any
> witness $y$ certifying that $z \in C$ (via some verifier $VC$ ), the same
> reduction $f$ converts the witness $y$ to a Boolean assignment of the
> variables of the formula $f(z)$ that satisfy it. In other words, this
> reduction translates not only between the decision problems, but also
> between the associated search problems.

The Arora-Barak book makes a similar remark, on page 50 under "More Thoughts on the Cook-Levin Theorem":

> The reduction $f$ from an $\mathsf{NP}$-language $L$ to $SAT$ presented in Lemma 2.11
> not only satisfied that $x \in L \iff f(x) \in SAT$ but actually the proof
> yields an efficient way to transform a certificate for $x$ to a
> satisfying assignment for $f(x)$ and vice versa. We call a reduction
> with this property a Levin reduction. One can also modify the proof
> slightly (see Exercise 2.13) so that it actually supplies us with a
> one-to-one and onto map between the set of certificates for $x$ and the
> set of satisfying assignments for $f(x)$, implying that they are of the
> same size.

There are other references to this fact of the Cook-Levin theorem. Recall that the proof of the Cook-Levin theorem takes a computation history of a Turing machine, a polytime verifier, and produces a polysized CNF formula which is satisfiable if and only if the verifier accepted.

I do not see how the Cook-Levin theorem implies this transformation from witnesses to witnesses, as it does from problems to problems. I would appreciate any directions or pointers, I feel like I may be missing something obvious.

**Tags:** cook-levin


---

## 1 answers

### Answer by username_1 on 2023-04-01. Score: 1 | Accepted answer

This essentially stems from the fact that satisfying assignments of the produced formula encode accepting computation paths of the nondeterministic TM for the problem that we started with. As may assume that this NTM works by first "guessing" a certificate nondeterministically and then verifying it using a deterministic procedure, which allows us to "read off" the original certificate from a satisfying assignment.


---

