Перейти к навигации Перейти к поиску
В теории сложности вычислений , то класс сложность Е есть множество проблем решения , которые могут быть решены с помощью детерминированной машины Тьюринга в время- O ( п ) и, следовательно , равен класс сложности DTIME (2 O ( N ) ).
E , в отличие от аналогичного класса EXPTIME , не закрывается при полиномиальном времени много-однозначных редукций .
Ссылки [ править ]
- Allender, E .; Стросса, М. (1994), "Измерение на малых классов сложности с приложениями для БПП", Труды IEEE FOCS'94 , стр. 807-818, ЧПСК TR94-004 , DIMACS TR 94-18.
- Книга, R. (1972), "О языках , принятых в полиномиальное время", SIAM журнал по вычислениям , 1 (4): 281-287, DOI : 10,1137 / 0201019.
- Книга, R. (1974), "Сравнение классов сложности", Журнал вычислительной техники и системы наук , 3 (9): 213-229, DOI : 10.1016 / s0022-0000 (74) 80008-5.
- Impagliazzo, R .; Тардос, Г. (1989), "Решение против задач поиска в суперполиномиальное время", Труды IEEE FOCS 1989 , стр. 222–227..
- Ватанабе, О. (1987), "Сравнение полиномиальное время полноты представлений", Теоретическая информатика , 54 : 249-265, DOI : 10,1016 / 0304-3975 (87) 90132-0.
Внешние ссылки [ править ]