Временная и пространственная сложность алгоритмов/Задачи/PSPACE in EXPTIME/Решение Билан

Материал из DISCOPAL
Перейти к: навигация, поиск

  • "Эта ДМТ может принимать максимум $s(n)2^{O(s(n))}$ состояний" - это почему еще?
  • "может принимать максимум $s(n)2^{O(s(n))}$ состояний, значит она работает за время $s(n)2^{O(s(n))}$" - это почему?