Формальные языки и сложность вычислений. Лекция 9. Классы P, NP. Виды сводимости. Языки SAT и 3-SAT.

Дата лекции: 01.11.24 Лектор: Зухба Анастасия Викторовна Оператор: Дмитрий Достовалов Редактор: Илья Оплачкин 00:00:00 - Введение 00:01:30 - Класс P 00:02:00 - Примеры языков из P 00:07:50 - Класс NP 00:13:00 - Примеры задач 00:18:40 - m-сводимость 00:20:00 - Сводимость по Карпу (полиномиальная) 00:22:00 - T-сводимость 00:23:30 - Сводимость по Куку 00:25:40 - Свойства полиномиальной сводимости 00:34:30 - NP-трудные и NP-полные языки 00:41:30 - Язык TMSAT (пример NP-полной задачи) 01:11:00 - Язык SAT 01:14:50 - Язык 3-SAT Сайт ВШПИ: https://hsse.mipt.ru