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