2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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, 2020 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$
    – Emil Jeřábek
    Sep 25, 2020 at 15:31

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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$
    – Hans Schmuber
    Jul 6, 2021 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$
    – Emil Jeřábek
    Jul 6, 2021 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$
    – Emil Jeřábek
    Jul 6, 2021 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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