Алгоритмы и модели вычислений 2. Классы P и NP.

0:00 Машина Тьюринга 11:00 Время работы машины 14:00 Сложность задачи 19:00 Теорема Блума 22:00 Классы DTIME(t(n)) 24:00 Класс P 27:00 Сложность при разных моделях вычислений 31:00 Задача о палиндроме 36:00 Пауза 38:00 Иерархия классов 54:00 Недетерминированные машины Тьюринга 1:01:00 Классы NTIME(t(n)), NP 1:06:00 Эквивалентность с сертификатным определением