E (complexité) - E (complexity)
En théorie de la complexité computationnelle , la classe de complexité E est l'ensemble des problèmes de décision qui peuvent être résolus par une machine de Turing déterministe en temps 2 O ( n ) et est donc égale à la classe de complexité DTIME (2 O( n ) ).
E , contrairement à la classe similaire EXPTIME , n'est pas fermé sous des réductions plusieurs-un en temps polynomial .
Les références
- Allender, E.; Strauss, M. (1994), "Mesure sur les petites classes de complexité avec des applications pour BPP", Actes de l'IEEE FOCS'94 , pp. 807-818, ECCC TR94-004 , DIMACS TR 94-18.
- Livre, R. (1972), "Sur les langues acceptées en temps polynomial", SIAM Journal on Computing , 1 (4) : 281-287, doi : 10.1137/0201019.
- Livre, R. (1974), "Comparing complex classes", Journal of Computer and System Sciences , 3 (9): 213-229, doi : 10.1016/s0022-0000(74)80008-5.
- Impagliazzo, R. ; Tardos, G. (1989), "Décision contre problèmes de recherche en temps super-polynomial", Actes de l'IEEE FOCS 1989 , pp. 222-227.
- Watanabe, O. (1987), "Comparison of polynomial time completeness notions", Theoretical Computer Science , 54 : 249-265, doi : 10.1016/0304-3975(87)90132-0.