E (complexity)
≈ 1 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computational complexity theory, the complexity class E is the set of decision problems 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.
In computational complexity theory, the complexity class E is the set of decision problems 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 in NE, as E is the deterministic-time analogue of the nondeterministic class NE.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1376276685 under CC BY-SA 4.0; modifications have been made.