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$?
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ Isn't it the other way around? $\endgroup$– M.MonetCommented Mar 6, 2020 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$– Emil JeřábekCommented Mar 6, 2020 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$– Emil JeřábekCommented Mar 6, 2020 at 16:57
-
$\begingroup$ Oh yes sorry I read too fast. Should I delete the comments? $\endgroup$– M.MonetCommented Mar 6, 2020 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 TalCommented Mar 6, 2020 at 21:02
|
Show 1 more comment