E (złożoność)

W teorii złożoności obliczeniowej klasa złożoności E jest zbiorem problemów decyzyjnych , które mogą być rozwiązane przez deterministyczną maszynę Turinga w czasie 2 ^{O ( n )} i dlatego jest równa klasie złożoności DTIME ( 2 ^{O ( n )} ).

E , w przeciwieństwie do podobnej klasy EXPTIME , nie jest domknięta w wielomianowych redukcjach wiele-jeden .

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 .
Book, R. (1972), „O językach akceptowanych w czasie wielomianowym”, SIAM Journal on Computing , 1 (4): 281–287, doi : 10.1137/0201019 .
Book, R. (1974), „Porównywanie 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 a problemy wyszukiwania w czasie super wielomianowym”, Proceedings of IEEE FOCS 1989 , s. 222–227 .
Watanabe, O. (1987), „Porównanie pojęć kompletności czasu wielomianowego”, Theoretical Computer Science , 54 : 249–265, doi : 10.1016/0304-3975 (87) 90132-0 .

Linki zewnętrzne