<p>This is quite unlikely to hold, because <span class="math-container">$\mathrm{EXP_{poly}^{NEXP}}$</span> actually coincides with <span class="math-container">$\Theta^{\exp}_2$</span>, the exponential analogue of the class <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T#theta2p" rel="nofollow noreferrer"><span class="math-container">$\Theta^P_2$</span></a>, which is presumably a strict subclass of <span class="math-container">$\mathrm{EXP^{NP}}$</span> (which is the exponential analogue of <span class="math-container">$\Delta^P_2$</span>).</p>
<p><span class="math-container">$\Theta^{\exp}_2$</span> can be variously defined as
<span class="math-container">$$\Theta^{\exp}_2=\mathrm{EXP^{\|NP}=EXP^{NP[poly]}=PSPACE^{NEXP}=P^{NEXP}=\exists\cdot DEXP},$$</span>
where <span class="math-container">$\|$</span> denotes parallel (nonadaptive) access to the oracle, <span class="math-container">$\mathrm{[poly]}$</span> restricts the number of oracle queries to polynomial, the oracle tape is included in the space requirements of the <span class="math-container">$\mathrm{PSPACE}$</span> machine, and <span class="math-container">$\mathrm{DEXP}=\{L_0\smallsetminus L_1:L_0,L_1\in\mathrm{NEXP}\}$</span> is the exponential analogue of <span class="math-container">$\mathrm{DP}$</span>.</p>
<p>For the <span class="math-container">$\mathrm{EXP_{poly}^{NEXP}}\subseteq\Theta^{\exp}_2$</span> 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 <span class="math-container">$\mathrm{EXP_{poly}^{NEXP}\subseteq EXP^{\|NP}}$</span>.</p>
<p>For the <span class="math-container">$\Theta^{\exp}_2\subseteq\mathrm{EXP_{poly}^{NEXP}}$</span> inclusion, it is obvious that <span class="math-container">$\mathrm{P^{NEXP}\subseteq EXP_{poly}^{NEXP}}$</span>.</p>

CC BY-SA 4.0
2021-07-06T14:43:51.777Z
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?
Hans Schmuber
CC BY-SA 4.0
2021-07-06T16:55:20.357Z
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}}$.
Emil Jeřábek
CC BY-SA 4.0
2021-07-06T18:55:26.813Z
For a better upper bound, it’s not difficult to show that $\mathrm{P_{log}^{NEXP}}$ is included in [$\mathrm O^p_2$](https://complexityzoo.net/Complexity_Zoo:O#o2p).
Emil Jeřábek
CC BY-SA 4.0
2020-09-30T11:06:37.350Z
2020-09-30T11:06:37.350Z
Emil Jeřábek
<p>Suppose we have an NP-complete language <span class="math-container">$L_1$</span> and a NEXP-complete language <span class="math-container">$L_2$</span>.
For any deterministic exptime machine <span class="math-container">$M_1$</span> with oracle access <span class="math-container">$M_1^{L_1}$</span>, is it possible to find a deterministic exptime oracle machine <span class="math-container">$M_2$</span> with access <span class="math-container">$M_2^{L_2}$</span> such that (a) <span class="math-container">$M_2$</span> may only make poly(n) length queries to <span class="math-container">$L_2$</span> (b) <span class="math-container">$M_2^{L_2}$</span> accepts iff <span class="math-container">$M_1^{L_1}$</span> accepts? (Note <span class="math-container">$M_1$</span> is capable of making exp(n) length queries to <span class="math-container">$L_1$</span> as it is an exponential time TM).</p>
<p>If the above is not true for a particular <span class="math-container">$L_2$</span>, is it possible to find an <span class="math-container">$M_2$</span> and an <span class="math-container">$L_2\in$</span>NEXP such that the above is true?</p>
<p>Obviously, there is always a polytime reduction from <span class="math-container">$L_1$</span> to <span class="math-container">$L_2$</span> as <span class="math-container">$L_2$</span> is NEXP-hard and <span class="math-container">$NP\subseteq NEXP$</span>. However if the queries to <span class="math-container">$L_1$</span> have <span class="math-container">$exp(n)$</span> length, then under the polytime reduction the corresponding <span class="math-container">$L_2$</span> instances will now also have <span class="math-container">$exp(n)$</span> length. Hence, if <span class="math-container">$M_2$</span> is restricted to only <span class="math-container">$poly(n)$</span> length queries it's not clear <span class="math-container">$M_2^{L_2}$</span> can always make the necessary queries.</p>
<p>It does not seem unreasonable that given an <span class="math-container">$(M_1, L_1)$</span> pair, that <span class="math-container">$M_2^{L_2}$</span> can simulate <span class="math-container">$M_1^{L_1}$</span> and return the same output. If we have an NP language with <span class="math-container">$exp(n)$</span> input, a non-deterministic TM of runtime <span class="math-container">$O(exp(n))$</span> is capable of solving it. A NEXP machine also has an <span class="math-container">$exp(n)$</span> runtime but on an input of length <span class="math-container">$poly(n)$</span> and so might be capable of solving the exponential length NP instance.</p>
<p>Edit: I suppose this boils down to the question, if <span class="math-container">$EXP_{poly}^A$</span> is an exponential time oracle machine which is only allowed to make polynomial length queries to <span class="math-container">$A$</span>, does the following hold: <span class="math-container">$EXP_{poly}^{NEXP} = EXP^{NP}$</span>? The containment <span class="math-container">$EXP_{poly}^{NEXP} \subseteq EXP^{NP}$</span> seems to be straightforward to prove.</p>

CC BY-SA 4.0
2020-09-25T14:18:06.430Z
For reference, here's a paper describing a class of NEXP-complete problems: [A note on succinct representations of graphs](https://doi.org/10.1016/S0019-9958(86)80009-2), 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).
Neal Young
CC BY-SA 4.0
2020-09-25T15:31:05.897Z
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.
Emil Jeřábek
<cc.complexity-theory><time-complexity><reductions><oracles><nexp>
Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?
Hans Schmuber
# Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?

(Asked by: username_0 on 2020-09-25)

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.

**Tags:** cc.complexity-theory, time-complexity, reductions, oracles, nexp

> **Comments:**
> **username_1**: For reference, here's a paper describing a class of NEXP-complete problems: [A note on succinct representations of graphs](https://doi.org/10.1016/S0019-9958(86)80009-2), 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).  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_2 on 2020-09-30. Score: 4 | Accepted answer

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$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T#theta2p), 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}}$.

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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}}$.  
> **username_2**: For a better upper bound, it’s not difficult to show that $\mathrm{P_{log}^{NEXP}}$ is included in [$\mathrm O^p_2$](https://complexityzoo.net/Complexity_Zoo:O#o2p).  

---

