# Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?

While reading "Computational Complexity: A Conceptual Perspective" by Oded Goldreich, I have come across the following passage, which I simply cannot get my head around:

Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent to the notion of self-reducibility. This is the case not only due to syntactic considerations, but also due to the following inherent reason. An oracle to any decision problem returns a single bit per invocation, while the intractability of a search problem in $$\mathcal{PC}$$ must be due to lacking more than a "single bit of information" [...].

For those unfamiliar with Goldreich's text, self-reducibility is used in the sense that a search problem $$R$$ is Cook-reducible to deciding membership in the respective solution set (i.e., the problem "given $$x$$, is $$x$$ a solution to $$R$$?"). $$\mathcal{PC}$$ is the class of polynomially verifiable search problems. The text in this chapter appears to be an expanded version of an article intitled "On Teaching the Basics of Complexity Theory" by the same author (Springer, non-paywall link).

Regarding the last quoted sentence, the text refers to an exercise to prove that, for any search problem which is in $$\mathcal{PC}$$ but not in $$\mathcal{PF}$$ (i.e., the class of search problems for which the solution can be found in poly-time) and which is self-reducible, the respective (Cook-)reduction performs at least (asymptotically) log queries to its oracle. (The proof is also not hard; if using only log queries, then the oracle may be replaced by a brute force subroutine without affecting the reduction's poly-time complexity.)

My question is two-fold:

1. What does Goldreich mean by "syntactic considerations"? Does he simply mean it is cumbersome to define self-reducibility by other means than using reductions?
2. What relation does the exercise referred to in the text have to the claim regarding "lacking more than a 'single bit of information'"? (After all, the exercise is about log many queries, not a single one.) And what does this have to do with the inherentness of reductions to self-reducibility?

I assume Goldreich is alluding to widely-known facts here. Apologies if this can only be answered by the man himself.

• As a small addition to Sasho's answer: "i.e." meaning "that is" (in contrast to "e.g." (which means "for example"), here the sentence should read in your head as "Note that the general notion of a reduction (that is, Cook reduction)", and not like "Note that the general notion of a reduction (for instance, Cook reduction)". I find this clarifies it a little bit. Jan 4, 2019 at 6:47