3
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by tparker, Community Aug 10 at 12:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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 Apr 23 '16 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 Apr 23 '16 at 10:59