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

00:00:00 - заставка 00:02:13 - задачи оптимизации 00:10:53 - задача о минимизации формулы 00:16:30 - задача Рамсея 00:24:49 - кликовая раскраска 00:30:40 - наследуемая кликовая раскрашиваемость 00:31:43 - задача о VC-размерности (Вапника-Червоненкиса) 00:46:20 - определение полиномиальной иерархии 00:52:45 - теорема P=NP ⇒ P=PH 00:56:42 - обобщённая теорема о коллапсировании PH 01:10:05 - полные задачи в полиномиальной иерархии Дата лекции: Лектор: Мусатов Даниил Владимирович Оператор: Порай Екатерина Монтажёр: Хатымов Ренат Плейлист: