Сложность вычислений 3. NP-полнота

Таймкоды: 00:00:00 - Начало лекции 00:00:55 - Полиномиальная сводимость 00:05:27 - NP трудность и полнота 00:11:38 - Отношение разных классов 00:12:55 - Теорема Ладнера 00:16:38 - Генерическая NP-полная задача, TMSAT 00:27:00 - SAT, 3SAT, CSP и q-CSP 00:31:02 - Cводимость 3COL к 3SAT 00:36:20 - Сводимость SAT к 3SAT 00:40:30 - Теорема Кука-Левина Дата лекции: 17.09.2025 Лектор: Мусатов Даниил Владимирович Оператор: Козырь Екатерина Монтажёр: Крещик Владимир Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvbboj4ZMEucHSR5p9ysMODF Плейлист