4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, this is basically an expansion of the parenthetical comment at the end of my post. I'm just trying to get a rough, non-rigorous mental picture of the relative difficulties of the problems. (Also, your second-to-last paragraph is the core of my OP - the point is that RFS isn't harder than, say NP-complete problems, which are in the PH. That's the issue.) $\endgroup$ – tparker Mar 16 '18 at 0:35
  • $\begingroup$ And clearly I'm not referring to engineering costs in my OP. Could you give specific examples of different difficulty orderings within the PH with respect to the various possible senses that you mention? I suspect that it practice, it doesn't matter too much which scheme you use. $\endgroup$ – tparker Mar 16 '18 at 0:47
  • 1
    $\begingroup$ @tparker, OK. I apologize for misunderstanding what you are asking, then. In that case, I'm not entirely sure how to help. Hopefully someone else can get you an answer that will be more useful to you! $\endgroup$ – D.W. Mar 16 '18 at 2:22
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't see how this answers my question. I'm not asking about the relative difficulty of PH and BQP - I'm asking about the relative difficulty of problems in NP-COMPLETE vs. certain problems in, say, $\Sigma_N$ for very large $N$. I'm comparing each of them to a problem in BQP that is outside of PH, but then eliminating the intermediate problem to conclude with a problem in $\Sigma_1$ that seems harder than a problem in $\Sigma_N$. $\endgroup$ – tparker Mar 17 '18 at 1:36
  • $\begingroup$ I disagree. All your problem RFS does is exemplify that PH and BQP are incomparable. Anyway, I wish you good luck in attracting answers to the question you intended to ask. $\endgroup$ – kne Mar 17 '18 at 12:35
  • $\begingroup$ Could you clarify which step you disagree with? (a) RFS is harder than some problem $x \in (\Sigma_N \setminus \Sigma_{N-1})$ with $N > 1$, (b) any $y$ in NP-COMPLETE is harder than RFS, or (c) there exists an $x \in (\Sigma_N \setminus \Sigma_{N-1})$ easier than any $y$ in NP-COMPLETE $\subset \Sigma_1$? $\endgroup$ – tparker Mar 17 '18 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.