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

Таймкоды: 00:00:00 - Начало лекции 00:01:05 - Напоминание 00:03:40 - NP-полнота Гамильтонова пути 00:07:27 - Сводимость Гамитльтонова пути к циклу 00:13:34 - Сводимость 3SAT к Гамильтонову пути 00:31:23 - Переход к ориентируемому случаю 00:38:00 - Задача TSP 00:42:55 - Задача NAE-SAT 00:52:34 - Сводимость NAE-SAT к 3COL 01:00:15 - Задача поиска 01:08:15 - Сводимость по Левину 01:11:40 - Задача о клике 01:17:50 - Различные постановки задач Дата лекции: 24.09.2025 Лектор: Мусатов Даниил Владимирович Оператор: Козырь Екатерина Монтажёр: Крещик Владимир Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvbboj4ZMEucHSR5p9ysMODF Плейлист в ВК: https://vkvideo.ru/playlist/-206078025_156