Wednesday, June 26, 2024

E versus EXP

Why do we have two complexity classes for exponential time, E and EXP?

First the definitions:

E is the set of problems computable in time \(2^{O(n)}\).

EXP is the set of problems computable in time \(2^{\mathrm{poly}(n)}\).

The nondeterministic variants NE and NEXP have similar definitions and properties.

By the time hierarchy theorem, E is strictly contained in  EXP. But they have basically the same complexity:

  • There are polynomial-time many-one complete sets for EXP in E.
  • EXP is the closure of E under polynomial-time many-one reductions.
  • E is in NP if and only if NP = EXP. You can replace NP by PSPACE, BPP, BQP or any other class closed under poly-time many-one reductions.
Quiz: Show that PSPACE \(\neq\) E. Hint: The proof doesn't tell you which class might be larger.

EXP is the natural class for exponential time since it is closed under polynomial-time reductions and is known to contain PSPACE and all those other classes above. You have results like MIP = NEXP but not MIP = NE since MIP (interactive proofs with multiple provers) is closed under polynomial-time reductions. 

E = NE implies EXP = NEXP but not necessarily the other way around. P = NP implies both equalities but again not the other way around. You get P = NP implies E = NE because poly(\(2^n)\) = \(2^{O(n)}\). That equality plays a role in other theorems related to E and NE:

Impagliazzo-Widgerson: If E is not computed by subexponential-size (\(2^{o(n)}\))-sized circuits then P = BPP. A similar assumption for EXP would only put BPP in quasipolynomial time. 

Hartmanis-Immerson-Sewelson: show that there are sparse (polynomial-sized) sets in NP-P if and only if E \(\ne\) NE. Their paper leads to endless confusion because they state the result as EXPTIME \(\ne\) NEXPTIME without defining the terms before the terminology was set.

In fact I just fixed the Wikipedia article on EXPTIME which had the incorrect statement. Aargh!


  1. Like this post

  2. I have the opposite question - why aren't there similar distinctions on other levels of complexity?

    Why aren't we talking much of LINEAR (like P, but O(n)), what about "small versions" of L, NL?

    Why is E so special?

    1. There's definitely similar issues with log space vs polylog space, and to lesser extent with P vs Linear. The challenge with E and EXP is that people will often just say "exponential time" to mean either class where we don't usually have that confusion with the other classes.

  3. This reason we don't have a class for linear time is that the notion is model-dependent: there are languages that are linear time on a multi-tape Turing machine but require quadratic time on a single-tape Turing machine