In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, the
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...
E is the set of
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
s that can be solved by a
deterministic Turing machine in time 2
O(''n'') and is therefore equal to the complexity class
DTIME(2
O(''n'')).
E, unlike the similar class
EXPTIME, is not closed under
polynomial-time many-one reductions.
Relationship to other classes
E is contained by
NE.
References
*.
*.
*.
*.
*.
External links
*
{{comp-sci-theory-stub
Complexity classes