Сложность вычислений 5. Полиномиальная иерархия

Таймкоды: 00:00:00 - Организационные моменты про Д/З 00:01:09 - Полиномиальная иерархия, введение 00:02:15 - Задача о минимизации формулы 00:06:09 - Задача точной оптимизации 00:10:52 - Обобщенная рамсеевость 00:18:01 - Кликовая раскраска 00:25:53 - Размерность Вапника-Червоненкиса 00:36:22 - Определения Sigma_k^p и Pi_k^p 00:39:46 - Изображение полиномиальной иерархии 00:43:32 - Вопрос о коллапсе иерархии 00:49:50 - Теорема об условиях коллапса 01:03:22 - Sigma_k^p- и Pi_k^p-полные задачи Дата лекции: 05.03.26 Лектор: Мусатов Даниил Владимирович Оператор: Ахмедов Али Монтажер: Трашкун Даниил Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvb2_RW66GZ6P_WkjwR3n9U7 Плейлист