10
$\begingroup$

It seems that many results in complexity hold assuming PH doesn't collapse to the second or third levels. At these low levels, I have some intuition about the collapse not occurring since additional quantifiers seem to add power not already inherent in the lower levels, but higher levels escape my understanding.

Basically, are there any known results that separate levels of PH assuming other complexity theoretic separations? Is there any intuition that PH doesn't collapse to some finite level other than its generalization from P vs. NP and logical hierarchies?

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ I have asked this type of question in several occasions from various people. The most satisfying answer I have received is that of my advisor Madhu Sudan paraphrased here: the main reason it is wise to assume different computational classes (such as levels of PH) are different is that there is no good reason for them being equal. Although coincidences sometimes occur -- especially when one combines computational resources which are not easily comparable -- (here I am hinting at IP=PSPACE) it seems reasonable in normal contexts to trust the general principle of "more resources, more power". $\endgroup$
    – Mohammad Bavarian
    Commented Jun 30, 2014 at 23:10
  • $\begingroup$ By the way, I understand that you might be more interested in some form of a harder evidence. But I thought it may be useful to you (or somebody out there) to hear the above philosophy which I personally have found quite useful. $\endgroup$
    – Mohammad Bavarian
    Commented Jun 30, 2014 at 23:13
  • $\begingroup$ Related: cstheory.stackexchange.com/a/11403/129. $\endgroup$
    – Joshua Grochow
    Commented Sep 10, 2019 at 15:49
  • $\begingroup$ @MohammadBavarian: While I generally agree with that reasoning, it is interesting to note that the "NL hierarchy" collapses to the first level because NL=coNL. So the question then becomes: why should this reasoning apply to a hierarchy above NP but not to a hierarchy above NL? There may be a good reason, but it is at least something to think about. $\endgroup$
    – Joshua Grochow
    Commented Sep 10, 2019 at 15:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.