I have a problem which is in NEXP$^{\text{NP}}$ and can also be solved by an alternating TM using exponential time and just one alternation (starting in an existential state).

Is there anything known about NEXP$^{\text{NP}}$? Is it equal to NEXP or some other class? Are there complete problems other than the generic one (given an NEXP$^{\text{NP}}$ machine and a word, does it accept?).


A natural $\text{NEXP}^{\text{NP}}$-complete problem is deciding a sentence of Presburger arithmetic with an $\exists^*\forall^*\exists^*$-quantifier prefix (as shown here). Further complete problems related to database theory have been studied here.


$NEXP^{NP}$ is (probably) bigger than NEXP, as we can ask questions of exponential length from the oracle. That NP in the power is practically a NEXP there, so eg. co-NEXP is contained in $NEXP^{NP}$.

  • $\begingroup$ You argued well in response to Peter Shor's answer that $NEXP^{EXP}$ is likely strictly more powerful than $NEXP$. I'm confused, though. It seems that analogously this should mean that $NP^P$ is larger than $NP$, although (I think) they're equal. Where am I going wrong here? $\endgroup$ – Huck Bennett Apr 11 '11 at 21:39
  • 7
    $\begingroup$ @Huck Polynomials are closed under polynomials. Exponentials aren't. So, I can feed the EXP oracle an exponentially long argument, and it can do work exponential in that argument, which is doubly exponential in the original problem. $\endgroup$ – Mark Reitblatt Apr 11 '11 at 21:58
  • $\begingroup$ @domotorp I thought $NEXP^{NP}\subseteq NEXP^{EXP}=NEXP$? How about $EXP^{EXP}$? $\endgroup$ – T.... Dec 11 '17 at 1:25
  • $\begingroup$ The problem is that the input of the oracle gets padded, so for example $DTIME(2^n)^{DTIME(2^n)}=DTIME(2^{2^{n}})$. $\endgroup$ – domotorp Dec 11 '17 at 5:43
  • $\begingroup$ @Turbo I don't see the mistake right now but looks like with this logic we could prove that for any $f(n)$ we have $DTIME(f(n))\subset P/poly$, which is a bit suspicious... Maybe you should ask this as a question. $\endgroup$ – domotorp Dec 12 '17 at 8:41

Expanding my comment above a little bit: If you have only one query to the $NP$-oracle (as in your case), then it follows from the work of Hemaspaandra, that your problem is in $P^{NE}$. This means that your problem is Turing reducible to any $NE$-hard problem. I think it is not known whether this is true for all of $NEXP^{NP}$.


The largest query a $NEXP^{NP}$ machine can make to the oracle is exponential in the length of the input. The power of the oracle is only polynomial in this, which should also be exponential. In other words, $poly(2^{n^k})=O(2^{n^{k+1}})$. Hence, another $NEXP$ machine should be able to simulate your machine as well as the oracle.

Edited for parentheses...

  • 3
    $\begingroup$ NTMs don't quite work like that. NTMs split, and if one copy accepts the whole thing accepts. When you split, you don't get to look at the results of your non-det copies. So, if I made one query to a NP machine, and immediately returned the opposite answer, how would you simulate that? $\endgroup$ – Mark Reitblatt Apr 12 '11 at 23:02
  • 1
    $\begingroup$ As @Mark points out, the fact that the machine is non-deterministic makes a big difference here, as the oracle queries can be made non-deterministically. This is exactly why $NP^{NP}$ is not trivially equal to $NP$. $\endgroup$ – Joe Fitzsimons Apr 13 '11 at 0:04
  • $\begingroup$ Ah, yes. When simulating an oracle query, if the correct result is no, then all branches will return no. On the other hand, if the correct result is yes, then at least one branch will return yes. In particular, some may return no. Thus, when as @Mark suggests, you negate the result of the query, you are likely to get false positives. $\endgroup$ – Aubrey da Cunha Apr 13 '11 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy