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.
1 Answer
$\begingroup$
$\endgroup$
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.
