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

Извиняемся. Последний кусок лекции не записался. В качестве компенсации предлагаем вам изучить оставшийся материал по текущей версии книжки лектора (с 394 страницами): Раскраски, c. 103. Теорема (там доказана сводимость 3SAT к 3COL без использования посредника NAE-3SAT); Покрытие множествами и задача о рюкзаке, c. 109. 00:00:00 - заставка 00:02:00 - напоминание с предыдущей лекции 00:07:16 - определения CLIQUE, INDSET, VERTEXCOVER 00:13:47 - полнота VERTEXCOVER 00:34:10 - теорема о частном случае 00:43:54 - план доказательства полноты 3COL 00:45:56 - сводимость 3SAT к NAE-3SAT 00:57:00 - сводимость NAE-3SAT к 3COL (не доведено) Дата лекции: Лектор: Мусатов Даниил Владимирович Оператор: Иванов Максим Монтажёр: Хатымов Ренат Плейлист: