11
$\begingroup$

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

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

4 Answers 4

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\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
    Commented Apr 11, 2011 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
    Commented Apr 11, 2011 at 21:58
  • $\begingroup$ @domotorp I thought $NEXP^{NP}\subseteq NEXP^{EXP}=NEXP$? How about $EXP^{EXP}$? $\endgroup$
    – Turbo
    Commented Dec 11, 2017 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
    Commented Dec 11, 2017 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
    Commented Dec 12, 2017 at 8:41
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 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
    Commented Apr 12, 2011 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
    Commented Apr 13, 2011 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
    Commented Apr 13, 2011 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.