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

  • 1
    $\begingroup$ Why the downvotes? Am I missing something here? $\endgroup$ Sep 9, 2019 at 3:46
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 11, 2019 at 16:49
  • $\begingroup$ @JoshuaGrochow Would your comment in cstheory.stackexchange.com/q/198 and relations among $P$, $NP$, $NL$, $GapL$ and $GapP$ address $P=NP\neq PP$? $\endgroup$
    – Turbo
    Sep 15, 2019 at 8:56

1 Answer 1


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

  • 4
    $\begingroup$ 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. $\endgroup$
    – Lwins
    Oct 28, 2019 at 13:26

Your Answer

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

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