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!
Like this post
ReplyDeleteI have the opposite question - why aren't there similar distinctions on other levels of complexity?
ReplyDeleteWhy aren't we talking much of LINEAR (like P, but O(n)), what about "small versions" of L, NL?
Why is E so special?
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.
Delete