I have a meta-complexity question: Are there reasons to believe that it is more difficult to prove P != NP than, say PSPACE != EXPTIME or BPP != BQP?

  • 1
    $\begingroup$ See this related question: cs.stackexchange.com/questions/1877/how-not-to-solve-p-np. There are known barriers for separating $\mathsf{P},\mathsf{NP}$. I dont know if natural proofs or algebraization could be applied to $\mathsf{PSPACE},\mathsf{EXP}$, but diagonalization won't work. $\endgroup$
    – Ariel
    Commented Apr 23, 2016 at 10:58
  • 1
    $\begingroup$ This is since we can find oracles relative to which $PSPACE=EXP$, and oracles for which they are different. $EXP^{EXP}\neq PSPACE^{EXP}$, and there are oracles for which $PSPACE=EXP$ (see "Randomness is Hard" by Buhrman and Torenvliet, they show the existence of an oracle relative to which $EXP^{NP}\subseteq BPP\subseteq PSPACE$, although this might be an overkill). $\endgroup$
    – Ariel
    Commented Apr 23, 2016 at 10:59