Karp reduction from optimization problems to decision problems

When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other.

Focusing on Cook reductions, there exists a natural Karp reduction from the decision version of a problem to optimization version. Is the converse also true?

• NP-completeness is a category of decision problems. When we say that an optimization problem is NP-complete, what we really mean is that its decision version is NP-complete. – Yuval Filmus May 7 '20 at 7:25
• Thanks. Let me edit the question then removing the last part. – usercs May 7 '20 at 10:38
• What do you mean by a Karp reduction from the optimization version to the decision version? Can you give a definition or an example? – Yuval Filmus May 7 '20 at 10:44
• Consider the problem of deciding whether there is vertex cover of size less than $\leq k$ and the problem of finding the minimum vertex cover. – usercs May 7 '20 at 11:30
• You still haven't define what a Karp reduction would be in this context. I know what a Karp reduction is for two decision problems, but that's not the case you're interested in. – Yuval Filmus May 7 '20 at 11:31