1
$\begingroup$

What is an example of a Karp reduction $f$ between two problems $A, B$ in $\textbf{NP}$ such that $f$ does not provide a way to transform certificates of one problem into certificates of the other? In other words, such that $f$ is not the Karp reduction in any Levin reduction between $A, B$?

The accepted answer to this question mentions that it is not always the case that such a Karp reduction yields a corresponding Levin reduction:

"It is true that the well-known Karp reductions between natural problems turn out to be Levin reduction but this does not need to be true in general."

However, I'm struggling to find/devise a concrete ("natural", if possible) example of why this is the case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.