Every mathematician understands the concept of reducing a complicated problem to a simpler problem. "Without loss of generality, we may assume…" However, I've noticed that some kinds of "reductions" seem to be less meaningful than others, and I'm wondering if there's any way to make a precise distinction.
I'll begin with a somewhat silly example just to illustrate the point. Dick Askey once told me that he had seen the following poorly phrased question on a school math test: "Why is $\pi$ irrational?" I couldn't guess the intended answer until Dick told me: "Because its decimal expansion does not repeat." I laughed in surprise, then remarked, "Well, I guess that's not actually wrong…" Dick responded, "Can you prove it? In that order?"
The point here is that in principle there is nothing to stop you from saying, "Since irrational numbers have non-repeating decimal expansions, to prove that $\pi$ is irrational, it suffices to prove that the decimal expansion of $\pi$ does not repeat." But as any mathematician knows, this is an extremely unpromising line of thinking. This is a "reduction" in name only.
Now let me give a more serious example, that was the proximate cause for my posting this question. Ryan Williams has a very nice paper on natural proofs and derandomization that I have been trying to digest. There is a certain issue that arises in the paper that I am bit uneasy about and have been discussing with Ryan over email, without a definitive conclusion so far. I will phrase it in as non-technical a manner as possible. Suppose we have two complexity classes, $H$ (for "hard") and $E$ (for "easy"). We want to show that $H\not\subseteq E$, but have had no luck so far. Examination of the literature shows that a typical way that people show this sort of thing is to define some sort of predicate $P$, and then to prove
$(*)$ $\qquad\qquad(\exists x\in H: P(x)) \wedge (\forall x\in E: \neg P(x)).$
Further study of the problem reveals that there is an important distinction between predicates that are constructive and those that are nonconstructive. (I won't define what this means here because it is not relevant for my purposes; all that matters is that there are two kinds of predicates.) The conventional wisdom is that the nonconstructive predicates are the promising ones for proving $H\not\subseteq E$. However, in his paper, Williams proves the following:
If $H\not\subseteq E$, then there is a constructive predicate $P$ satisfying $(*)$.
There is no question that this is a non-trivial and interesting result. What I am not sure about, though, is what it really tells us about how we should focus our energies in the search for a proof that $H\not\subseteq E$. In particular, I'm not sure that it tells us that in our search for suitable predicates, it suffices to consider constructive predicates. Could it be that the "only" way to prove that $(*)$ holds for some constructive predicate $P$ is to first prove $(*)$ for a nonconstructive predicate and then apply Williams's theorem, just as the "only" way to prove that the decimal expansion of $\pi$ does not repeat is to first prove that $\pi$ is irrational and then apply the theorem that irrational numbers have non-repeating decimal expansions?
Here is a hypothetical stronger result, that I don't think anyone knows how to state precisely, let alone prove, but that would convince me that it suffices to consider constructive predicates:
For any predicate $P$ and any proof of $(*)$ for that predicate, there exists a constructive predicate $P'$ such that replacing $P$ with $P'$ in the proof results in a correct proof of $(*)$ for $P'$.
If we could give a general construction of $P'$ from $P$, then it seems clear that whenever we come up with a $P$ that we think is promising, then we might as well consider $P'$ instead, since any argument that we might think to apply to $P$ will apply to $P'$ as well. However, Williams's theorem alone doesn't seem to give us this stronger result.
I instinctively feel that I'm putting my finger on an important distinction here, that is of relevance in the search for lower bounds in complexity theory, but at the same time I also feel that I'm being incorrigibly vague. In my weaker moments, that makes me doubt that the distinction I'm drawing is real, and even in my stronger moments, it makes me wonder if there is a more precise and compelling way to state the point I'm making. As I've opined elsewhere on MO, I don't think there's much hope of being able to state formally anything along the lines of "Every proof of this theorem must follow such-and-such a pattern." Nevertheless, is there a better way to state the distinction I'm trying to draw, assuming the distinction is real?
