Theoretical Computer Science
reductions oracles polynomial-time search-problem complexity-theory
Updated Sun, 22 May 2022 01:08:44 GMT

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.

Solution

I think you may be misunderstanding the sentence "Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent." This is not about reductions being inherent to self-reducibility (in the sense Goldreich uses it), but rather about Cook reductions being inherent to this notion, in the sense that they cannot be replaced by Karp reductions. Goldreich makes a distinction between a "general notion of reduction", meaning a Cook reduction, and the restricted notion of a Karp reduction. Then he points out that the fact that Cook reductions in his definition of self-reducibility cannot be replaced by Karp reductions is not merely because of some formality (i.e. "syntactic considerations") but is inherent because a Karp reduction only makes a single query to the decision problem oracle, and, hence, only reveals "a single bit of information". The exercise shows that many more than a single bit of information need to be revealed (log many bits, as you point out).

Comments (3)

  • +1 – Aha. It seems I got lost in Goldreich's (at times) crabbed prose. Many thanks :) — Jan 04, 2019 at 08:26  
  • +2 – My impression is that, while he's very precise, his style is terse and a little idiosyncratic, so if you don't pay very close attention you can easily get lost. I had trouble with his crypto books in grad school. — Jan 04, 2019 at 11:06  
  • +2 – I feel this sentence would actually be much easier to parse if "general" was in italics, which would make clearer the fact that the point made refers to "general" (and not to "general reduction"). — Jan 04, 2019 at 11:13  

External Links

External links referenced by this document:

References