E (сложность) - E (complexity)

В теория сложности вычислений, то класс сложности E это набор проблемы решения это может быть решено детерминированная машина Тьюринга вовремя 2О (п) и, следовательно, соответствует классу сложности DTIME (2O (п)).

E, в отличие от аналогичного класса EXPTIME, не закрывается под многочленные редукции с полиномиальным временем.

использованная литература

  • Allender, E .; Штраус, М. (1994), "Мера на классах малой сложности с приложениями для BPP", Труды IEEE FOCS'94, стр. 807–818, ECCC  TR94-004, DIMACS TR 94-18.
  • Книга Р. (1972), "О языках, принятых за полиномиальное время", SIAM Журнал по вычислениям, 1 (4): 281–287, Дои:10.1137/0201019.
  • Книга Р. (1974), "Сравнение классов сложности", Журнал компьютерных и системных наук, 3 (9): 213–229, Дои:10.1016 / с0022-0000 (74) 80008-5.
  • Импальяццо, Р.; Тардос, Г. (1989), "Решение против задач поиска в суперполиномиальное время", Труды IEEE FOCS 1989, стр. 222–227.
  • Ватанабэ, О. (1987), "Сравнение понятий полиномиальной полноты времени", Теоретическая информатика, 54: 249–265, Дои:10.1016/0304-3975(87)90132-0.

внешние ссылки