Should we always think of problems higher in the polynomial hierarchy as harder than problems lower in the hierarchy?

Question

This "research vignette" (whatever that is) claims that the polynomial hierarchy

classifies problems according to a natural notion of logical complexity, and is defined with an infinite number of levels: problems at the zeroth level are the “easiest”, and for every integer $k$, problems at the $(k+1)$-st level have logical complexity “one notch higher” than those at level $k$.

Obviously this is just a heuristic explanation rather than any kind of rigorous claim, but is it true that problems higher in the hierarchy should be thought of as harder than problems lower in the hierarchy?

For example, consider the complexity class BQP. It is not believed to contain NP; in fact, many experts consider (Fig. 3) NP-complete problems to be much harder than the hardest problems in BQP. But the same experts also believe that BQP is not contained within the polynomial hierarchy PH (with Recursive Fourier Sampling as a concrete example of a problem believed to be in BQP \ PH). It therefore seems reasonable to say that for any $n$, there exist problems in $\Sigma_n \setminus \Sigma_{n-1}$ that are easier than RFS.

But putting these two results (that any NP-complete problem is harder than RFS, and that RFS is harder than some problem in $\Sigma_n \setminus \Sigma_{n-1}$ for any $n$) together, we find that there are problems in $\Sigma_1$ (namely, any NP-complete problem) that are harder (in fact, much, much harder) than certain problems in $\Sigma_n \setminus \Sigma_{n-1}$ for all $n$. Therefore, I don't see any way in which the polynomial hierarchy actually ranks problems by complexity.

Is there is mistake in my reasoning? Is there any useful sense in which problems higher up in the hierarchy are always harder than problems lower down? (I know this is a soft question, since there are different ways of formalizing the notion that one problem is "harder" than another. Maybe the answer is just that the PH is one way of ranking certain problems by difficulty, but not generally the best way.)

Answer 1

The quote you give is an informal claim/intuition. Don't try to read too much into informal claims; they are intended to give you a sense of what's going on, but for specific details, you need to look at the precise technical claim.

I suspect the source of your confusion is that you are using the same phrase in two or three different ways in different places, without realizing it. This is the logical fallacy of equivocation. In particular, I don't think you're using "harder than" in exactly the same way each time you use it. This then leads to you reaching conclusions that seem absurd or confusing. One way to remedy the confusion is to understand more clearly exactly what you mean by "harder than", and then walk through your logic.

One possible meaning of "P is harder than Q" is that the "running time of the fastest algorithm to solve P is larger than the running time of the fastest algorithm to solve Q, in some specific theoretical model of computation". This is a statement about theoretical complexity. Note that this meaning depends on the model of computation. P might be harder than Q in one model of computation (e.g., classical computation), but not in another model (e.g., quantum computation).

A second possible meaning of "P is harder than Q" is "Q reduces to P". This is a theoretical statement, which has implications for the previous statement (if Q reduces to P, then the running time of the fastest algorithm for P can't be too much less than the running time of the fastest algorithm for Q). Note that this notion of "harder than" is as a partial order. There might be two problems P,Q such that neither "P is harder than Q" nor "Q is harder than P" are true; the problems might be incomparable.

A third possible meaning of "P is harder than Q" is "in practice it's probably harder (takes more time or costs more) to solve instances of P than instances of Q". This is a statement about engineering and what is feasible in practice, rather than theory. For instance, this will depend on whether quantum computers are feasible to build, in practice -- something that no one knows the answer to right now. If quantum computers are feasible, then we'll discover that factoring is much easier than all NP-complete problems, because a quantum computer can solve factoring quickly but can't solve NP-complete problems quickly (we think). If quantum computers aren't feasible, then factoring might turn out to be not much easier than some NP-complete problems.

Finally, just because a problem isn't in PH doesn't necessarily mean it is harder than all problems in PH -- so just because Recursive Fourier Sampling is not in PH doesn't necessarily mean it is harder than all problems in PH (in the sense of the existence of a reduction).

As a final complication, Recursive Fourier Sampling is a funny kind of problem. It's not an ordinary decision problem. Rather, it's an oracle problem. Oracle problems can't be directly compared to ordinary problems.

Answer 2

The answer to your actual question is yes. The only thing I would (nitpickingly) change about the text you cite is that, when it talks about the $(k+1)$-st level, it should acknowledge that it includes the $k$-th level. So the "one notch higher" happens only for problems that are new in the $(k+1)$-st level.

One thing the polynomial hierarchy does not do is encompass all problems. It "classifies problems according to [...] complexity", but only those problems, which it happens to contain.

The popular conjecture seems to be that BQP is incomparable with PH. (There are problems in NP which are conjectured not to be in BQP and problems in BQP which are conjectured not to be in PH.) And that is not even surprising. PH and BQP extend P in different ways. PH by (bounded-alternation) nondeterminism, BQP by quantum. A priori there is no reason to assume the resulting classes to be comparable.