E versus EXP

Computational Complexity 2024-06-26

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 than 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!