Сложность вычислений 8. Теорема Сэвича. Полнота в PSPACE. Логарифмическая память

Таймкоды: 00:00:00 - Напоминание 00:02:35 - Теорема Сэвича 00:18:35 - Класс PSPACE 00:23:28 - Сводимость в PSPACE 00:24:39 - PSPACE-полнота 00:27:00 - Байки про машину времени 00:28:45 - TQBF, доказательство полноты 00:39:52 - GG - Обобщённая игра в города 01:03:00 - Логарифмическая память Дата лекции: 29.10.2025 Лектор: Мусатов Даниил Владимирович Оператор: Козырь Екатерина Монтажёр: Крещик Владимир Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvbboj4ZMEucHSR5p9ysMODF Плейлист в ВК: https://vkvideo.ru/playlist/-206078025_156