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.


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

Comments (3)

  • +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

External links referenced by this document: