# Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?

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.

• 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). Sep 25 '20 at 14:18
• 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. 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}}$$.
• 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? Jul 6 at 14:43
• 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}}$. Jul 6 at 16:55
• For a better upper bound, it’s not difficult to show that $\mathrm{P_{log}^{NEXP}}$ is included in $\mathrm O^p_2$. Jul 6 at 18:55