<p>The trouble with exponential-time reductions is that they may exponentially expand the input, and this leads to all sorts of weirdness.</p>
<p>So, to begin with, neither EXP nor NEXP is closed under exp-time reductions in the first place. The languages exp-time reducible to EXP-languages comprise EEXP (doubly exponential time, also written as 2-EXP) by an obvious padding argument, and likewise, the languages exp-time reducible to NEXP comprise NEEXP.</p>
<p>A related fact is that exp-time reductions are not closed under composition, hence the corresponding relation <span class="math-container">$\le_{\exp}$</span> between languages is not transitive: for example, if <span class="math-container">$L_0$</span>, <span class="math-container">$L_1$</span>, and <span class="math-container">$L_2$</span> are languages complete for P, EXP, and EEXP (respectively) under poly-time reductions, then <span class="math-container">$L_2\le_{\exp} L_1\le_{\exp}L_0$</span>, but <span class="math-container">$L_2\nleq_{\exp}L_0$</span>.</p>
<p>(The transitive closure of exp-time reductions consists of all Kalmár-elementary reductions, and likewise, the smallest class containing EXP or NEXP that is closed under exp-time reductions is ELEMENTARY.)</p>
<p>To answer the question, the classs of problems NEXP-complete under exp-time reductions is <em>unconditionally</em> different from either NEXP or from the class of usual NEXP-complete problems:</p>
<p>On the one hand, SAT is NEXP-complete under exp-time reductions, but since it belongs to <span class="math-container">$\mathrm{NP}\subsetneq\mathrm{NEXP}$</span> by the nondeterministic time-hierarchy theorem, it is not NEXP-complete under poly-time reductions.</p>
<p>(More generally, the class of languages NEXP-time complete under exp-time reductions includes all languages in NEXP that are NP-hard in the usual sense.)</p>
<p>On the other hand, the trivial languages <span class="math-container">$\varnothing$</span> and <span class="math-container">$\Sigma^*$</span> are not NEXP-complete under any kind of many-one reductions. If you want a nontrivial example, you have to assume <span class="math-container">$\mathrm{EXP\ne NEXP}$</span> (as any language in EXP exp-time reduces to any nontrivial language), but that is clearly also sufficient: if you take any nontrivial language <span class="math-container">$L\in\mathrm{P\subseteq NEXP}$</span>, then <span class="math-container">$L$</span> is not NEXP-complete under exp-time reductions unless <span class="math-container">$\mathrm{EXP=NEXP}$</span>.</p>
<p>If we restrict the exp-time reductions to time <span class="math-container">$2^{O(n)}$</span> (rather than <span class="math-container">$2^{n^{O(1)}}$</span>) and refer to NE instead of NEXP, there is a simple characterization. The following are equivalent:</p>
<ol>
<li><p><span class="math-container">$L$</span> is NE-complete under exp-time (i.e., time-<span class="math-container">$2^{O(n)}$</span>) reductions.</p>
</li>
<li><p><span class="math-container">$L\in\mathrm{NE}$</span>, and <span class="math-container">$L$</span> is hard for <em>unary</em> NP languages under poly-time reductions.</p>
</li>
</ol>
<p>For 1→2, if <span class="math-container">$L_1\in\mathrm{NP}$</span> is a unary language, let <span class="math-container">$L_2=\{w\in\{0,1\}^*:1^w\in L_1\}$</span> be its binary encoding; then <span class="math-container">$L_2\in\mathrm{NE}$</span>, thus there is a time-<span class="math-container">$2^{cn}$</span> reduction <span class="math-container">$f$</span> of <span class="math-container">$L_2$</span> to <span class="math-container">$L$</span>. Then <span class="math-container">$x\mapsto f(|x|)$</span> is a reduction of <span class="math-container">$L_1$</span> to <span class="math-container">$L$</span> working in polynomial time <span class="math-container">$2^{c(\log n)}=n^c$</span>.</p>
<p>For 2→1, if <span class="math-container">$L_2\in\mathrm{NE}$</span>, its unary encoding <span class="math-container">$L_1=\{1^w:w\in L_2\}$</span> is in NP, thus <span class="math-container">$L_1$</span> reduces to <span class="math-container">$L$</span> via a poly-time reduction <span class="math-container">$f$</span>. Then <span class="math-container">$w\mapsto f(1^w)$</span> is a <span class="math-container">$2^{O(n)}$</span>-time reduction of <span class="math-container">$L_2$</span> to <span class="math-container">$L$</span>.</p>
<p>For NEXP and time-<span class="math-container">$2^{n^{O(1)}}$</span> reductions, a similar characterization should work using hardness for unary nondeterministic quasipolynomial-time languages under quasipolynomial-time reductions.</p>

CC BY-SA 4.0
2021-02-11T11:59:00.123Z
2021-02-11T12:06:42.397Z
2021-02-11T12:06:42.397Z
Emil Jeřábek
<p>One thing that surprised me when learning about complexity theory is that for a complexity class C, we tend to define C-complete using polynomial time reductions, even when C is a very large complexity class.</p>

<p>This definitely makes sense for P and NP, but how about EXPTIME and NEXPTIME? </p>

<p>So my question is this: What is the subset of NEXPTIME comprised of problems exp-time reducible from every other problem in NEXPTIME? If EXPTIME != NEXPTIME, is this class distinct from both NEXPTIME and NEXPTIME-complete?</p>

CC BY-SA 3.0
2014-07-23T08:07:50.727Z
I'm not sure I understand your question. Hardness and therefore completness is defined with respect to the same type of reducibility. Then you ask for the set of languages which are in NEXPTIME(subset) and, if I understand correctly, are NEXPTIME-hard(reduce 'from'). Obviously, this is the class NEXPTIME-complete. Depending on whether you consider  completeness w.r.t ptime many-to-one reductions or exptime many-to-one, or any other type of reduction, this class can differ.
John D.
CC BY-SA 3.0
2014-07-23T11:51:50.660Z
Right, to clarify my question is about the "this class can differ".

Has anyone proved whether or not the set NEXPTIME-complete (w/ ptime-reduction) is distinct from the set NEXPTIME-complete (w/ exptime-reduction)?
Kurt Mueller
CC BY-SA 3.0
2014-07-28T16:04:42.810Z
Sorry if this question is too simplistic. Suppose $x$ is an instance of an NEXPTIME problem, it seems that the reduction process must preserve the size of the instance by running in polynomial-time. Do you have any problem instance that requires EXPTIME to produce (by reduction) another problem instance?
lgidwani
CC BY-SA 3.0
2014-07-29T14:00:55.383Z
A trivial example is that we have an exponential time reduction from every single problem in EXPTIME to any other problem by simply solving the EXPTIME problem.

The existence of a less trivial example is the goal of asking this question :)
Kurt Mueller
<cc.complexity-theory><time-complexity><nexp>
NEXPTIME-completeness with more time for reductions
Kurt Mueller
# NEXPTIME-completeness with more time for reductions

(Asked by: username_0 on 2014-07-22)

One thing that surprised me when learning about complexity theory is that for a complexity class C, we tend to define C-complete using polynomial time reductions, even when C is a very large complexity class.

This definitely makes sense for P and NP, but how about EXPTIME and NEXPTIME?

So my question is this: What is the subset of NEXPTIME comprised of problems exp-time reducible from every other problem in NEXPTIME? If EXPTIME != NEXPTIME, is this class distinct from both NEXPTIME and NEXPTIME-complete?

**Tags:** cc.complexity-theory, time-complexity, nexp
> **Comments:**
> **username_1**: I'm not sure I understand your question. Hardness and therefore completness is defined with respect to the same type of reducibility. Then you ask for the set of languages which are in NEXPTIME(subset) and, if I understand correctly, are NEXPTIME-hard(reduce 'from'). Obviously, this is the class NEXPTIME-complete. Depending on whether you consider  completeness w.r.t ptime many-to-one reductions or exptime many-to-one, or any other type of reduction, this class can differ.  
> **username_0**: Right, to clarify my question is about the "this class can differ".  Has anyone proved whether or not the set NEXPTIME-complete (w/ ptime-reduction) is distinct from the set NEXPTIME-complete (w/ exptime-reduction)?  
> **username_2**: Sorry if this question is too simplistic. Suppose $x$ is an instance of an NEXPTIME problem, it seems that the reduction process must preserve the size of the instance by running in polynomial-time. Do you have any problem instance that requires EXPTIME to produce (by reduction) another problem instance?  
> **username_0**: A trivial example is that we have an exponential time reduction from every single problem in EXPTIME to any other problem by simply solving the EXPTIME problem.  The existence of a less trivial example is the goal of asking this question :)  

---

## 1 answers

### Answer by username_3 on 2021-02-11. Score: 8 | Accepted answer

The trouble with exponential-time reductions is that they may exponentially expand the input, and this leads to all sorts of weirdness.

So, to begin with, neither EXP nor NEXP is closed under exp-time reductions in the first place. The languages exp-time reducible to EXP-languages comprise EEXP (doubly exponential time, also written as 2-EXP) by an obvious padding argument, and likewise, the languages exp-time reducible to NEXP comprise NEEXP.

A related fact is that exp-time reductions are not closed under composition, hence the corresponding relation $\le\_{\exp}$ between languages is not transitive: for example, if $L\_0$, $L\_1$, and $L\_2$ are languages complete for P, EXP, and EEXP (respectively) under poly-time reductions, then $L\_2\le\_{\exp} L\_1\le\_{\exp}L\_0$, but $L\_2\nleq\_{\exp}L\_0$.

(The transitive closure of exp-time reductions consists of all Kalmár-elementary reductions, and likewise, the smallest class containing EXP or NEXP that is closed under exp-time reductions is ELEMENTARY.)

To answer the question, the classs of problems NEXP-complete under exp-time reductions is *unconditionally* different from either NEXP or from the class of usual NEXP-complete problems:

On the one hand, SAT is NEXP-complete under exp-time reductions, but since it belongs to $\mathrm{NP}\subsetneq\mathrm{NEXP}$ by the nondeterministic time-hierarchy theorem, it is not NEXP-complete under poly-time reductions.

(More generally, the class of languages NEXP-time complete under exp-time reductions includes all languages in NEXP that are NP-hard in the usual sense.)

On the other hand, the trivial languages $\varnothing$ and $\Sigma^\*$ are not NEXP-complete under any kind of many-one reductions. If you want a nontrivial example, you have to assume $\mathrm{EXP\ne NEXP}$ (as any language in EXP exp-time reduces to any nontrivial language), but that is clearly also sufficient: if you take any nontrivial language $L\in\mathrm{P\subseteq NEXP}$, then $L$ is not NEXP-complete under exp-time reductions unless $\mathrm{EXP=NEXP}$.

If we restrict the exp-time reductions to time $2^{O(n)}$ (rather than $2^{n^{O(1)}}$) and refer to NE instead of NEXP, there is a simple characterization. The following are equivalent:

1. $L$ is NE-complete under exp-time (i.e., time-$2^{O(n)}$) reductions.
2. $L\in\mathrm{NE}$, and $L$ is hard for *unary* NP languages under poly-time reductions.

For 1→2, if $L\_1\in\mathrm{NP}$ is a unary language, let $L\_2=\{w\in\{0,1\}^\*:1^w\in L\_1\}$ be its binary encoding; then $L\_2\in\mathrm{NE}$, thus there is a time-$2^{cn}$ reduction $f$ of $L\_2$ to $L$. Then $x\mapsto f(|x|)$ is a reduction of $L\_1$ to $L$ working in polynomial time $2^{c(\log n)}=n^c$.

For 2→1, if $L\_2\in\mathrm{NE}$, its unary encoding $L\_1=\{1^w:w\in L\_2\}$ is in NP, thus $L\_1$ reduces to $L$ via a poly-time reduction $f$. Then $w\mapsto f(1^w)$ is a $2^{O(n)}$-time reduction of $L\_2$ to $L$.

For NEXP and time-$2^{n^{O(1)}}$ reductions, a similar characterization should work using hardness for unary nondeterministic quasipolynomial-time languages under quasipolynomial-time reductions.


---

