# Are there theoretical reasons for believing that P=NP is harder than other complexity problems? [duplicate]

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?

• 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. – Ariel Apr 23 '16 at 10:58
• 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). – Ariel Apr 23 '16 at 10:59