Are there polynomial time reductions where the corresponding witnesses can't be translated in polynomial time? At the heart of NP-completeness is the idea that one can reduce instances of any problem in NP to, for example, 3-SAT. But this definition doesn't require that it must be possible to convert witnesses for yes-instances in polynomial time also. Does this fact follow regardless?
I'm looking at this in particular from the point of view of zero-knowledge proofs. Here the existence of computationally zero-knowledge proofs for all problems in NP is demonstrated by showing that 3-colorability has such proofs. But the guarantee that I can translate problems - or "conjectures" - in polynomial time is useless. I need to be able to translate witnesses - or "proofs". How is the possibility of this assured?
The proof of the Cook-Levin theorem shows that any problem in NP can be reduced to SAT in such a way that witnesses to the original problem can be converted efficiently to satisfying assignments of the resulting SAT instance. The proof of the NP-completeness of 3-colorability goes via a series of reductions, each of which also has this property.