Сложность вычислений 6. Полнота в PH и Альтернирующие Машины Тьюринга

Таймкоды: 00:00:00 - Объявление о первой к/р 00:00:40 - Напоминание определений из прошлой лекции 00:06:38 - Теорема о существовании Sigma и Pi полных задач 00:29:54 - Оговорка о том, что не существует естественных полных задач при больших k 00:33:23 - Альтернирующие Машины Тьюринга 00:43:42 - Sigma_k TIME и Pi_k TIME и утверждения про них 00:59:32 - Класс AP и его равенство PSPACE 01:01:42 - Почему повышается цена на память? 01:06:10 - Гипотеза P = PSPACE Дата лекции: 12.03.26 Лектор: Мусатов Даниил Владимирович Оператор: Ахмедов Али Монтажер: Трашкун Даниил Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvb2_RW66GZ6P_WkjwR3n9U7 Плейлист