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?

  • $\begingroup$ 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. $\endgroup$ – John D. Jul 23 '14 at 8:07
  • $\begingroup$ 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)? $\endgroup$ – Kurt Mueller Jul 23 '14 at 11:51
  • $\begingroup$ 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? $\endgroup$ – lgidwani Jul 28 '14 at 16:04
  • $\begingroup$ 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 :) $\endgroup$ – Kurt Mueller Jul 29 '14 at 14:00

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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