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

В начале пары идёт организационная информация про контрольную. Можете перемотать по соответствующему таймкоду на содержательную часть лекции. Таймкоды: 00:00:00 - Организационная информация 00:05:40 - Полиномиальная иерархия 00:12:34 - Задача о минимизации формулы 00:17:05 - Задача о кликовой раскраске 00:23:50 - Задача о наследуемой раскраске 00:28:30 - Обобщённая Рамсеевость 00:37:30 - Задача о VC-размерности 00:47:00 - Сигма и пи k классы 00:50:25 - Класс PH 00:55:20 - Теорема о равенстве P и PH 01:00:20 - Теорема о равенстве PH и NP 01:04:38 - Теорема о коллапсировании иерархии Дата лекции: 08.10.2025 Лектор: Мусатов Даниил Владимирович Оператор: Козырь Екатерина Монтажёр: Крещик Владимир Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvbboj4ZMEucHSR5p9ysMODF Плейлист