<p>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.  </p>

<p>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?  </p>

CC BY-SA 3.0
2014-06-30T23:10:47.613Z
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".
Mohammad Bavarian
CC BY-SA 3.0
2014-06-30T23:13:24.933Z
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.
Mohammad Bavarian
CC BY-SA 4.0
2019-09-10T15:49:25.660Z
Related: https://cstheory.stackexchange.com/a/11403/129.
Joshua Grochow
CC BY-SA 4.0
2019-09-10T15:51:26.643Z
@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.
Joshua Grochow
<cc.complexity-theory>
Collapsing PH Implications
Zak Webb
# Collapsing PH Implications

(Asked by: username_0 on 2014-06-24)

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?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: 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".  
> **username_1**: 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.  
> **username_2**: Related: https://cstheory.stackexchange.com/a/11403/129.  
> **username_2**: @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.  

---

## 0 answers

