# Complexity Class NEXP$^\text{NP}$

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?).

• Check out the work on the exponential time hierarchy, for instance ecommons.library.cornell.edu/bitstream/1813/6617/1/86-777.pdf
– 5501
Apr 11, 2011 at 19:08
• Note that $NEXP^{NP}$ does have another name in the literature (based on the alternation characterization), namely $\Sigma_2 EXP$. Jan 31, 2013 at 20:10

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}$.

• 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? Apr 11, 2011 at 21:39
• @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. Apr 11, 2011 at 21:58
• @domotorp I thought $NEXP^{NP}\subseteq NEXP^{EXP}=NEXP$? How about $EXP^{EXP}$? Dec 11, 2017 at 1:25
• The problem is that the input of the oracle gets padded, so for example $DTIME(2^n)^{DTIME(2^n)}=DTIME(2^{2^{n}})$. Dec 11, 2017 at 5:43
• @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. Dec 12, 2017 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...

• 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? Apr 12, 2011 at 23:02
• 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$. Apr 13, 2011 at 0:04
• 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. Apr 13, 2011 at 19:55