Theoretical Computer Science
cc.complexity-theory time-complexity reductions oracles nexp
Updated Fri, 27 May 2022 12:44:31 GMT

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.

Solution

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

• +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? — Jul 06, 2021 at 14:43
• +1 – 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 06, 2021 at 16:55
• +1 – For a better upper bound, its not difficult to show that $\mathrm{P_{log}^{NEXP}}$ is included in $\mathrm O^p_2$. — Jul 06, 2021 at 18:55

External links referenced by this document: