Theoretical Computer Science
cc.complexity-theory time-complexity nexp
Updated Sun, 22 May 2022 08:51:19 GMT

# NEXPTIME-completeness with more time for reductions

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?

## Solution

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 Kalmr-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 12, 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 21, 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.