It is clear that $NEXP\subseteq EXP^{NP}$, as a TM with exponential run time can simply query the NP oracle with an exponentially long query. However, it's not clear that the reverse $EXP^{NP}\subseteq NEXP$ is true. Are there any complexity theoretic conjectures which suggest this is not true and hence $EXP^{NP}\not=NEXP$?

  • 1
    $\begingroup$ Isn't it the other way around? $\endgroup$
    – M.Monet
    Mar 6 '20 at 13:32
  • $\begingroup$ I don’t really understand what do you expect to get. $\mathrm{EXP^{NP}\ne NEXP}$ is itself a complexity theoretic conjecture. This is implied, for example, by $\mathrm{NEXP\ne coNEXP}$. $\endgroup$ Mar 6 '20 at 16:54
  • $\begingroup$ @M.Monet Isn’t what the other way round? But if you mean the inclusions, they are stated correctly in the question: $\mathrm{NEXP\subseteq EXP^{NP}}$ is true, while $\mathrm{EXP^{NP}\subseteq NEXP}$ is likely false. $\endgroup$ Mar 6 '20 at 16:57
  • $\begingroup$ Oh yes sorry I read too fast. Should I delete the comments? $\endgroup$
    – M.Monet
    Mar 6 '20 at 17:39
  • 1
    $\begingroup$ @user138901 - See my similar question here: cstheory.stackexchange.com/questions/41500/… There are many evidence that strengthen this conjecture, and I am still looking for more... $\endgroup$
    – Avi Tal
    Mar 6 '20 at 21:02

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.