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

Таймкоды: 00:00:00 - Начало лекции 00:01:50 - Определение T(n) 00:07:27 - Асимптотические обозначения 00:13:55 - Определение классов P, QP, E, EXP, EEXP, SUBEXP 00:25:41 - Неконструктивное док-во принадлежности к P задачи о вложимости графов 00:34:28 - Теорема Робертсона-Сеймура 00:41:25 - Задача о доминирующем множестве 00:45:52 - Задача об изоморфизме графов 00:49:42 - Примеры задач из E, EXP 00:55:40 - Определения класса NP 01:03:55 - Эквивалентность определений 01:08:46 - NP вложено в EXP 01:10:40 - Классы NEXP и coNP 01:16:00 - Структура вложений классов Дата лекции: 10.09.2025 Лектор: Мусатов Даниил Владимирович Оператор: Козырь Екатерина Монтажёр: Крещик Владимир Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvbboj4ZMEucHSR5p9ysMODF Плейлист в ВК: https://vkvideo.ru/playlist/-206078025_156