E (complexity class)

The complexity class is the class of all languages that can be solved by a deterministic Turing machine in exponential time with a linear exponent. So for each there is a Turing machine with a time limit for any one , so that the machine accepts the word in at most steps for all of them . ${\displaystyle \mathbf {E} }$ ${\displaystyle L\in \mathbf {E} }$ ${\displaystyle M_{L}}$ ${\displaystyle t_{L}(n)\in O(k^{n})}$ ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle w\in L}$ ${\displaystyle M_{L}}$ ${\displaystyle w}$ ${\displaystyle t_{L}(|w|)}$

The class plays an important role in complexity theory because it is not closed under polynomial time reduction like EXPTIME . Because with that you can conclude: PSPACE . While is known for :, is not too known for any relation . ${\displaystyle \mathbf {E} }$ ${\displaystyle \not =\mathbf {E} }$ ${\displaystyle \mathbf {EXPTIME} }$ ${\displaystyle \mathbf {PSPACE} \subseteq \mathbf {EXPTIME} }$ ${\displaystyle \mathbf {E} }$ ${\displaystyle \mathbf {PSPACE} }$

Web links

• E . In: Complexity Zoo. (English)