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) 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.

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.