Suppose we have an NP-complete language $L_1$ and a NEXP-complete language $L_2$. For any deterministic exptime machine $M_1$ with oracle access $M_1^{L_1}$, is it possible to find a deterministic exptime oracle machine $M_2$ with access $M_2^{L_2}$ such that (a) $M_2$ may only make poly(n) length queries to $L_2$ (b) $M_2^{L_2}$ accepts iff $M_1^{L_1}$ accepts? (Note $M_1$ is capable of making exp(n) length queries to $L_1$ as it is an exponential time TM).

If the above is not true for a particular $L_2$, is it possible to find an $M_2$ and an $L_2\in$NEXP such that the above is true?

Obviously, there is always a polytime reduction from $L_1$ to $L_2$ as $L_2$ is NEXP-hard and $NP\subseteq NEXP$. However if the queries to $L_1$ have $exp(n)$ length, then under the polytime reduction the corresponding $L_2$ instances will now also have $exp(n)$ length. Hence, if $M_2$ is restricted to only $poly(n)$ length queries it's not clear $M_2^{L_2}$ can always make the necessary queries.

It does not seem unreasonable that given an $(M_1, L_1)$ pair, that $M_2^{L_2}$ can simulate $M_1^{L_1}$ and return the same output. If we have an NP language with $exp(n)$ input, a non-deterministic TM of runtime $O(exp(n))$ is capable of solving it. A NEXP machine also has an $exp(n)$ runtime but on an input of length $poly(n)$ and so might be capable of solving the exponential length NP instance.

Edit: I suppose this boils down to the question, if $EXP_{poly}^A$ is an exponential time oracle machine which is only allowed to make polynomial length queries to $A$, does the following hold: $EXP_{poly}^{NEXP} = EXP^{NP}$? The containment $EXP_{poly}^{NEXP} \subseteq EXP^{NP}$ seems to be straightforward to prove.

  • 1
    $\begingroup$ For reference, here's a paper describing a class of NEXP-complete problems: A note on succinct representations of graphs, by Papadimitriou and Yannakakis. For example, "succinct" CNF-SAT, where the input is a tuple $(n, m, C)$, where $n$ and $m$ are integers and $C$ is a circuit that implicitly defines a formula $\Phi_C$ on $n$ variables and $m$ clauses as follows: for any $i\le n$ and $j\le m$, the output of circuit $C$ on input $i, j$ specifies whether the $i$th variable occurs in the $j$th clause of $\Phi_C$, and if so how (negated or not). $\endgroup$
    – Neal Young
    Sep 25 '20 at 14:18
  • 8
    $\begingroup$ Answering the question in the title (which seems completely different from the question in the question body): reduction of an NP-complete language to an NEXP language with exponentially smaller input length will also give a reduction to a sparse NP language, as there are only polynomially many input strings of logarithmic length. It is known that there is no NP-complete sparse language unless P = NP. $\endgroup$ Sep 25 '20 at 15:31

This is quite unlikely to hold, because $\mathrm{EXP_{poly}^{NEXP}}$ actually coincides with $\Theta^{\exp}_2$, the exponential analogue of the class $\Theta^P_2$, which is presumably a strict subclass of $\mathrm{EXP^{NP}}$ (which is the exponential analogue of $\Delta^P_2$).

$\Theta^{\exp}_2$ can be variously defined as $$\Theta^{\exp}_2=\mathrm{EXP^{\|NP}=EXP^{NP[poly]}=PSPACE^{NEXP}=P^{NEXP}=\exists\cdot DEXP},$$ where $\|$ denotes parallel (nonadaptive) access to the oracle, $\mathrm{[poly]}$ restricts the number of oracle queries to polynomial, the oracle tape is included in the space requirements of the $\mathrm{PSPACE}$ machine, and $\mathrm{DEXP}=\{L_0\smallsetminus L_1:L_0,L_1\in\mathrm{NEXP}\}$ is the exponential analogue of $\mathrm{DP}$.

For the $\mathrm{EXP_{poly}^{NEXP}}\subseteq\Theta^{\exp}_2$ inclusion, note that there are only exponentially many strings of polynomial length, hence the exponential-time machine may first ask all possible queries of that length in parallel, and then proceed with the computation, showing $\mathrm{EXP_{poly}^{NEXP}\subseteq EXP^{\|NP}}$.

For the $\Theta^{\exp}_2\subseteq\mathrm{EXP_{poly}^{NEXP}}$ inclusion, it is obvious that $\mathrm{P^{NEXP}\subseteq EXP_{poly}^{NEXP}}$.

  • $\begingroup$ Follow up on this. Does this hold for similar classes: e.g. if we only allow log length queries from a polytime TM, represented by $P_{log}$, does the following hold: $P_{log}^{NEXP}=P^{||NP}$, or something similar? How does one prove it? $\endgroup$
    – user138901
    Jul 6 at 14:43
  • 1
    $\begingroup$ There are only polynomially many possible log-length queries, hence you can give answers to all of them in advance as advice. That is, $\mathrm{P_{log}^{NEXP}\subseteq P/poly}$ (and for that matter, $\mathrm P_{\log}^X\subseteq\mathrm{P/poly}$ for any oracle $X$). Thus, this class is highly unlikely to coincide with $\mathrm{P^{\|NP}}$. $\endgroup$ Jul 6 at 16:55
  • 1
    $\begingroup$ For a better upper bound, it’s not difficult to show that $\mathrm{P_{log}^{NEXP}}$ is included in $\mathrm O^p_2$. $\endgroup$ Jul 6 at 18:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.