1
$\begingroup$

Arora-Barak says that using the Cook-Levin reduction, one can show that all NP-complete problems are downward self-reducible. I know that SAT is downward self-reducible but I am not able to see how we can use this fact together with the Cook-Levin theorem to prove that all NP-complete languages are downward self-reducible.

$\endgroup$
0
1
$\begingroup$

Recall the (downward) self-reduciblity of a language.

A language $L \in \mathrm{NP}$ is self-reducible if for every verifer $V$ for $L$, there is a polynomial-time Turing machine $M$ such that for any oracle $O_{L}$ deciding $L$, and any $x \in L$, we have $V(x, M^{O_{L}}(x)) = 1$.

The book gives a proof of the self-reduciblity of SAT. The idea for proving the self-reduciblity of all the $\mathrm{NP}$-complete language is similar.

Given an $\mathrm{NP}$-complete language $L$ and its verfer $V$, suppose that $L_{V}$ is the language of $V$. For every string $w \in \Sigma^{*}$, we define $L_{w} = \{ z = x \Vert w : \exists u \in \Sigma^{*}, (x, w\Vert u) \in L_{V} \}$. Clearly, $L_{w} \in \mathrm{NP}$. Since $L \in \mathrm{NP}\text{-complete}$, there exists a Karp reduction $f$ such that $$z \in L_{w} \Leftrightarrow f(z) \in L$$ Assume we have an oracle $O_{L}$ deciding $L$. Now we design an algorithm that, given $x \in L$, finds $w$ with $(x, w) \in L_{V}$. Say the length of $w$ (given $x$) is $n = \mathrm{poly}(|x|)$. The algorithm proceeds as follows:

For i = 1 to n do:
    Set b[i] = 0;
    Set w = b[1]b[2]...b[i];
    If f(xw) is not in L (We run this step using our oracle for L)
        Set b[i] = 1;
    End if;
End for;
Return w;

Indeed, $w$ is a witness of $x$, i.e. $(w, x) \in L_{V}$. And this algorithm runs in polynomial time.

Other languages in $\mathrm{NP}$ (that are not $\mathrm{NP}$-complete) may be self-reducible as well. An example is given by graph isomorphism, a language that is not known (or believed) to be in $\mathrm{P}$ or $\mathrm{NP}$-complete. On the other hand, it is believed that not all languages in $\mathrm{NP}$ are self-reducible.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.