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

Таймкоды: 00:00:00 - Повторение задачи EXACTSETCOVER 00:02:29 - Задача о рюкзаке KNAPSACK и SUBSETUM 00:06:30 - Частный случай задачи 00:13:29 - Сведение EXACTSETCOVER к SUBSETSUM 00:19:30 - Задачи SETCOVER и HITTINGSET 00:22:55 - NP-полнота задачи HITTINGSET 00:28:14 - Задача QUADEQ и сведение SAT к ней 00:36:50 - Задачи распознавания и поиска и их связь 00:44:05 - Теорема о сводимости задач поиска к задачам распознавания. Сводимость по Куку 00:49:23 - Пример задачи о клике и самосводимость 00:55:46 - Задачи подсчета: о перманенте матрицы и совершенных паросочетаниях 01:04:42 - Задачи аппроксимации 01:11:45 - Существование задач, в которых аппроксимация NP-трудна Дата лекции: 26.02.26 Лектор: Мусатов Даниил Владимирович Оператор: Ахмедов Али Монтажер: Трашкун Даниил Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvb2_RW66GZ6P_WkjwR3n9U7 Плейлист в ВК: https://vkvideo.ru/playlist/-206078025_247