Is Karp Reduction identical to Levin Reduction

Question

Definition: Karp Reduction

A language $A$ is Karp reducible to a language $B$ if there is a polynomial-time computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ such that for every $x$, $x\in A$ if and only if $f(x)\in B$.

Definition: Levin Reduction

A search problem $V_A$ is Levin reducible to a search problem $V_B$ if there is polynomial time function $f$ that Karp reduces $L(V_A)$ to $L(V_B)$ and there are polynomial-time computable functions $g$ and $h$ such that

1. $\langle x, y \rangle \in V_A \implies \langle f(x), g(x,y) \rangle \in V_B$,

2. $\langle f(x), z \rangle \in V_B \implies \langle x, h(x,z) \rangle \in V_A$

Are these reductions equivalent?

---

I think the two definitions are equivalent. For any two $\mathsf{NP}$ languages $A$ and $B$, if $A$ is Karp reducible to $B$, then $A$ is Levin reducible to $B$.

Here is my proof:

Let $x$ and $\overline{x}$ be arbitrary instances of $A$ while $x'$ be that of $B$. Suppose $V_A$ and $V_B$ are verifiers of $A$ and $B$. Let $y$ and $\overline{y}$ be arbitrary certificates of $x$ and $\overline{x}$ according to $V_A$. Let $z$ be that of $x'$ according to $V_B$.

Construct new verifiers $V'_A$ and $V'_B$ with new certificates $y'$ and $z'$:

$V'_A(x,y'):$

1. $y'=\langle 0,\overline{x},\overline{y}\rangle$: If $f(x)\ne f(\overline{x})$, reject. Otherwise output $V_A(\overline{x},\overline{y})$.
2. $y'=\langle 1,z\rangle$: Output $V_B(f(x),z)$.

$V'_B(x',z'):$

1. $z'=\langle 0,z\rangle$: Output $V_B(x',z)$.

2. $z'=\langle 1,x,y\rangle$: If $x'\ne f(x)$, reject. Otherwise output $V_A(x,y)$.

The polynomial-time computable functions $g$ and $h$ are defined as below:

$g(x,y')$

1. $y'=\langle 0,\overline{x},\overline{y}\rangle$: Output $\langle 1,\overline{x},\overline{y}\rangle$.

2. $y'=\langle 1,z\rangle$: Output $\langle 0,z\rangle$.

$h(x',z')$

1. $z'=\langle 0,z\rangle$: Output $\langle 1,z\rangle$.

2. $z'=\langle 1,x,y\rangle$: Output $\langle 0,x,y\rangle$.

Let $Y_x$ be the set of all certificates of $x$ according to $V_A$ and $Z_{x'}$ be the set of all certificates of $x'$ according to $V_B$. Then the set of all certificates of $x$ according to $V'_A$ is $0\overline{x}Y_\overline{x}+1Z_{f(x)}$ such that $f(x)=f(\overline{x})$, and the set of all certificates of $x'$ according to $V'_B$ is $0Z_{x'}+1\overline{x}Y_\overline{x}$ such that $x'=f(\overline{x})$.

(This is derived from the accepting language of $V'_A$ and $V'_B$.)

Now let $x'=f(x)$, the rest part is easy to check.

Answer 1

No. First note that Levin reduction only makes sense with respect to classes which certificate has a meaning, e.g. $\mathsf{NP}$ while Karp reduction is general. The word "certificate" for a problem makes sense only when a verifier is fixed. Levin's reduction assumes that the verifiers are fixed. You cannot change the verifiers. (In the following I assume that certificate verifiers are fixed as required by definition of Levin reduction.)

Second, Levin reduction means that one can find the certificate for one from the certificate for the other. 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.

If we can reduce instances of a problem $A$ to problem $B$ it doesn't mean we have a way of computing a certificate for one from a certificate for the other.

For this to be true we need the fact that a certificate search problem corresponding to the decision problem is polynomial time reducible to the decision problem. This is true for $\mathsf{NP\text{-}complete}$ problems but not known to be true generally even for $\mathsf{NP}$ problems.

Answer 2

A quick counterexample for your proof: suppose that $x_1, x_2 \in L_1$, $f(x_1) = f(x_2) \in L_2$, and $w$ is a valid certificate for $x_1$ but not for $x_2$

$M_1'(x_1,\langle 0,w \rangle)= M_1(x_1,w)=1$

$M_1'(x_2,\langle 0,w \rangle)= M_1(x_2,w)=0$

By definition $g(x_1,\langle 0,w \rangle) = \langle 1,x_1,w \rangle$

$f(x_1)=f(x_2)$ so $M'_2(f(x_2),\langle 1,x_1, w \rangle)) = M_1(x_1,w) = 1$ so $\langle 1,x_1, w \rangle$ is a valid certificate for $f(x_2)$ but

$h(f(x_2), \langle 1,x_1, w \rangle) = \langle 0, w \rangle$ which is not a valid certificate for $x_2$