Сложность вычислений 2. Классы P и NP

Таймкоды: 00:00:00 - Недетерминированные Машины Тьюринга (НМТ) 00:07:49 - Классы NTIME(T(n)), NP, NE, NEXP и их свойства 00:14:04 - Сертификатное определение NP 00:16:42 - Равносильность определений NP 00:22:12 - Ко-классы, CoNP 00:27:45 - SAT и TAUT, их двойственность 00:32:13 - Диаграмма классов, класс FACTORING 00:37:31 - Критерий P=NP 00:41:15 - Сводимость по Карпу. Классы CLIQUE и INDSET, их сводимость 00:45:53 - 4COL и его сводимость к SAT 00:50:32 - Свойства сводимости 00:53:45 - NP-трудность (NPH) и NP-полнота (NPC) 00:55:10 - Утверждения про NPH и NPC 01:02:40 - Что если P=NP? 01:05:53 - Генерическая NP-полная задача TMSAT, принадлежность к NP 01:08:56 - Сводимость A к TMSAT 01:11:49 - Что будет дальше... Дата лекции: 12.02.26 Лектор: Мусатов Даниил Владимирович Оператор: Ахмедов Али Монтажер: Трашкун Даниил Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvb2_RW66GZ6P_WkjwR3n9U7 Плейлист