3
$\begingroup$

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

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.