# Are all NP-complete languages downward self-reducible?

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

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 = bb...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.