E (złożoność) - E (complexity)
W teorii złożoności obliczeniowej The klasa złożoności E jest zestaw problemów decyzyjne , które mogą zostać rozwiązane przez deterministycznej maszyny Turingowi w czasie 2 O ( n ) , a zatem, w liczbie równej klasy złożoność DTIME (2 O ( n ) ).
E , w przeciwieństwie do podobnej klasy EXPTIME , nie jest domknięta w ramach wielomianowych redukcji wiele-jednych .
Bibliografia
- Allender, E.; Strauss, M. (1994), "Środek na małych klasach złożoności z aplikacjami dla BPP", Proceedings of IEEE FOCS'94 , s. 807-818, ECCC TR94-004 , DIMACS TR 94-18.
- Książka, R. (1972), „O językach akceptowanych w czasie wielomianowym”, SIAM Journal on Computing , 1 (4): 281-287, doi : 10.1137/0201019.
- Książka, R. (1974), „Porównanie klas złożoności”, Journal of Computer and System Sciences , 3 (9): 213-229, doi : 10.1016/s0022-0000 (74) 80008-5.
- Impagliazzo, R .; Tardos, G. (1989), „Decyzja kontra problemy wyszukiwania w czasie super-wielomian”, Proceedings of IEEE FOCS 1989 , s. 222-227.
- Watanabe, O. (1987), "Porównanie pojęć zupełności czasu wielomianowego", Informatyka teoretyczna , 54 : 249-265, doi : 10.1016/0304-3975 (87) 90132-0.