9
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Why the downvotes? Am I missing something here? $\endgroup$ – Joshua Grochow Sep 9 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$ – Stella Biderman Sep 11 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$ – T.... Sep 15 at 8:56
2
$\begingroup$

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

$\endgroup$
  • 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 at 13:26

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.