Е (сложность)
В теории сложности вычислений класс сложности E — это набор задач решения , которые могут быть решены детерминированной машиной Тьюринга за время 2. На ) и поэтому равен классу сложности DTIME (2 На ) ).
E , в отличие от аналогичного класса EXPTIME , не замкнут при полиномиальном времени сокращений «многие единицы» .
Отношения с другими классами
[ редактировать ] | В этом разделе есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
![[icon]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small}
E содержится в NE .
Ссылки
[ редактировать ]- Аллендер, Э.; Штраус, М. (1994), «Меры малых классов сложности с приложениями для BPP», Труды IEEE FOCS'94 , стр. 807–818, ECCC TR94-004 , DIMACS TR 94-18 .
- Книга, Р. (1972), «О языках, принятых в полиномиальное время», SIAM Journal on Computing , 1 (4): 281–287, doi : 10.1137/0201019 .
- Книга, Р. (1974), «Сравнение классов сложности», Журнал компьютерных и системных наук , 3 (9): 213–229, doi : 10.1016/s0022-0000(74)80008-5 .
- Импальяццо, Р. ; Тардос, Г. (1989), «Задачи решения и поиска в суперполиномиальное время», Труды IEEE FOCS 1989 , стр. 222–227 .
- Ватанабэ, О. (1987), «Сравнение понятий полиномиальной временной полноты», Theoretical Computer Science , 54 (2–3): 249–265, doi : 10.1016/0304-3975(87)90132-0 .