# Cook-Levin Theorem implies a transformation from witnesses to witnesses

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.