Сложность вычислений 7. Полиномиальная иерархия (продолжение)

00:00:00 - заставка 00:00:53 - полиномиальная иерархия (напоминание) 00:03:13 - полные языки в полиномиальной иерархии 00:06:03 - теорема о полноте Σ_k-SAT и П_k-SAT 00:39:30 - задача о дополнении раскраски 00:41:42 - 3CNF-SAT и 3DNF-SAT 00:52:03 - альтернирующие машины 00:58:57 - класс Σ_k TIME(t(n)) 01:05:14 - PH через оракулы Дата лекции: Лектор: Мусатов Даниил Владимирович Оператор: Порай Екатерина Монтажёр: Хатымов Ренат Плейлист: