<p>The scaled down version of <span class="math-container">$\mathsf{PH}$</span> versus <span class="math-container">$\mathsf{PP}$</span> is <span class="math-container">$\mathsf{AC}^0$</span> versus <span class="math-container">$MAJ \circ \mathsf{AC}^0$</span>, and we know that for the latter there is an exponential separation. Of course, this separation doesn't propagate exponentially up, but you could take this as philosophical evidence that <span class="math-container">$\mathsf{PH}$</span> is different enough from <span class="math-container">$\mathsf{PP}$</span> that perhaps that remains true even if <span class="math-container">$\mathsf{P} = \mathsf{NP} = \mathsf{PH}$</span>. (In fact, following this line of reasoning, I'd guess you can build an oracle relative to which <span class="math-container">$\mathsf{P} = \mathsf{NP} \neq \mathsf{PP}$</span>.)</p>

CC BY-SA 4.0
2019-10-28T13:26:10.360Z
I think $\mathsf{PP}$ corresponds to $MAJ \circ polylog$ where $polylog$ is _any_ gate with polylogarithmic fan-in. And we know that $MAJ$ itself is already not in $\mathsf{AC}^0$. Therefore scaling up we get $\mathsf{PP} \not \subseteq \mathsf{PH}$ in some relativized world.
Lwins
CC BY-SA 4.0
2019-10-28T01:59:02.343Z
2019-10-28T01:59:02.343Z
Joshua Grochow
<p>We think that <span class="math-container">$\mathsf{PH}$</span> does not collapse, and that <span class="math-container">$\mathsf{PP}$</span> is not in <span class="math-container">$\mathsf{P}$</span>.</p>

<p>Suppose on the contrary that <span class="math-container">$\mathsf{PH}$</span> does collapse, say even <span class="math-container">$\mathsf{P}= \mathsf{NP}$</span>.</p>

<p><span class="math-container">$\mathsf{PP}$</span> still seems like it would be of reach. </p>

<p>What evidence do we have that <span class="math-container">$\mathsf{P} \neq \mathsf{PP}$</span>, under that assumption, i.e., evidence that does not apply to <span class="math-container">$\mathsf{P}$</span> vs. <span class="math-container">$\mathsf{NP}$</span>?</p>

<p><span class="math-container">$\underline{\mbox{Assumption}}$</span>: Note if <span class="math-container">$\mathsf{SAT}$</span> is in linear time then perhaps <span class="math-container">$\mathsf{P=PSPACE}$</span> might follow as composition of linear time is linear time? </p>

<p><span class="math-container">$\underline{\mbox{Following is only based on if above assumption follows}}$</span>:</p>

<ol>
<li><p>Perhaps the problem would be </p>

<p>1a. why believe <span class="math-container">$\mathsf{SAT}$</span> is in superlinear time</p>

<p>1b. and if there is reason to believe <span class="math-container">$\mathsf{SAT}$</span> is in superlinear time then why believe <span class="math-container">$\mathsf{PP}$</span> requires <span class="math-container">$\Omega(\log\log n)$</span> quantifications?</p></li>
<li><p>Do evidences provided by <a href="https://eccc.weizmann.ac.il/report/2018/107/" rel="noreferrer">https://eccc.weizmann.ac.il/report/2018/107/</a> and <a href="http://arxiv.org/abs/1504.03398" rel="noreferrer">http://arxiv.org/abs/1504.03398</a> still hold up in face of <span class="math-container">$\mathsf{P=NP}$</span> and <span class="math-container">$\mathsf{SAT}$</span> in linear time (<span class="math-container">$\mathsf{P=NP}$</span> seems to invalidate second)?</p></li>
</ol>

CC BY-SA 4.0
2019-09-09T03:46:19.600Z
Why the downvotes? Am I missing something here?
Joshua Grochow
CC BY-SA 4.0
2019-09-11T16:49:54.050Z
Is it plausible that $\mathsf{PH}$ collapses but that $\mathsf{P}\neq \mathsf{\# P}$? That sounds more tractable and an affirmative answer would be an affirmative answer to this question.
Stella Biderman
CC BY-SA 4.0
2019-09-15T08:56:28.670Z
@JoshuaGrochow Would your comment in https://cstheory.stackexchange.com/q/198 and relations among $P$, $NP$, $NL$, $GapL$ and $GapP$ address $P=NP\neq PP$?
Turbo
<cc.complexity-theory><sat><big-picture><polynomial-hierarchy><pspace>
Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?
Turbo
# Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?

(Asked by: username_0 on 2019-09-08)

We think that $\mathsf{PH}$ does not collapse, and that $\mathsf{PP}$ is not in $\mathsf{P}$.

Suppose on the contrary that $\mathsf{PH}$ does collapse, say even $\mathsf{P}= \mathsf{NP}$.

$\mathsf{PP}$ still seems like it would be of reach.

What evidence do we have that $\mathsf{P} \neq \mathsf{PP}$, under that assumption, i.e., evidence that does not apply to $\mathsf{P}$ vs. $\mathsf{NP}$?

$\underline{\mbox{Assumption}}$: Note if $\mathsf{SAT}$ is in linear time then perhaps $\mathsf{P=PSPACE}$ might follow as composition of linear time is linear time?

$\underline{\mbox{Following is only based on if above assumption follows}}$:

1. Perhaps the problem would be

   1a. why believe $\mathsf{SAT}$ is in superlinear time

   1b. and if there is reason to believe $\mathsf{SAT}$ is in superlinear time then why believe $\mathsf{PP}$ requires $\Omega(\log\log n)$ quantifications?
2. Do evidences provided by <https://eccc.weizmann.ac.il/report/2018/107/> and <http://arxiv.org/abs/1504.03398> still hold up in face of $\mathsf{P=NP}$ and $\mathsf{SAT}$ in linear time ($\mathsf{P=NP}$ seems to invalidate second)?

**Tags:** cc.complexity-theory, sat, big-picture, polynomial-hierarchy, pspace
> **Comments:**
> **username_1**: Why the downvotes? Am I missing something here?  
> **username_2**: Is it plausible that $\mathsf{PH}$ collapses but that $\mathsf{P}\neq \mathsf{\# P}$? That sounds more tractable and an affirmative answer would be an affirmative answer to this question.  
> **username_0**: @JoshuaGrochow Would your comment in https://cstheory.stackexchange.com/q/198 and relations among $P$, $NP$, $NL$, $GapL$ and $GapP$ address $P=NP\neq PP$?  

---

## 1 answers

### Answer by username_1 on 2019-10-28. Score: 2

The scaled down version of $\mathsf{PH}$ versus $\mathsf{PP}$ is $\mathsf{AC}^0$ versus $MAJ \circ \mathsf{AC}^0$, and we know that for the latter there is an exponential separation. Of course, this separation doesn't propagate exponentially up, but you could take this as philosophical evidence that $\mathsf{PH}$ is different enough from $\mathsf{PP}$ that perhaps that remains true even if $\mathsf{P} = \mathsf{NP} = \mathsf{PH}$. (In fact, following this line of reasoning, I'd guess you can build an oracle relative to which $\mathsf{P} = \mathsf{NP} \neq \mathsf{PP}$.)

> **Comments:**
> **username_3**: I think $\mathsf{PP}$ corresponds to $MAJ \circ polylog$ where $polylog$ is _any_ gate with polylogarithmic fan-in. And we know that $MAJ$ itself is already not in $\mathsf{AC}^0$. Therefore scaling up we get $\mathsf{PP} \not \subseteq \mathsf{PH}$ in some relativized world.  

---

