Вычислительная сложность

Эта лекция посвящена вычислительной сложности и является второй частью лекции о вычислимости Мы поговорим о важности недетерминизма в разнообразных машинах, о классах P, NP и PSPACE, о полиномиальной сводимости разных задач и о многом другом Предыдущая лекция: Следующая лекция: TBD Лектор: Константин Владимиров Дата лекции: 12 июня 2021 года Съёмка и звук: Дмитрий Рябцев Слайды к лекциям автора по логике и вычислимости: Timeline 00:00 Введение 04:45 Конечные автоматы 14:10 Эпсилон переходы и NFA 25:40 Автоматы с магазинной памятью 41:34 Недетерминированная машина Тьюринга, P и NP 55:20 SAT и варианты SAT 01:07:00 NP-полнота и теорема Кука 01:15:11 Cведения к SAT и друг другу самых разных задач 01:52:15 TAUT и co-NP 02:02:41 QBF и класс PSPACE 02:20:10 Заключение Errata: * тут пока пусто