Сложность вычислений 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:    • Сложность вычислений (3 курс, осень 2025) ...   Плейлист в ВК: https://vkvideo.ru/playlist/-20607802...