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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.