7
$\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$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.