Сложность вычислений 3. Полиномиальная сводимость, классы NPH и NPC

00:00:00 - заставка 00:00:43 - картинка класcов 00:02:29 - сводимость по Карпу 00:08:24 - сводимость 3COL к SAT 00:13:57 - сводимость 3COL к 4COL 00:16:48 - другие свойства сводимости 00:22:15 - NPH, NPC, NPI 00:26:29 - картинка классов в случае P=NP 00:31:26 - NP-полная задача TMSAT 00:37:45 - комментарий про пустое множество и его дополнение 00:40:03 - 3SAT 00:42:43 - сводимость SAT к 3SAT на примере 00:49:48 - теорема Кука-Левина Дата лекции: Лектор: Мусатов Даниил Владимирович Оператор: Порай Екатерина Монтажёр: Хатымов Ренат Плейлист: