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.