Формальные языки и сложность вычислений. Лекция 11. Класс CoNP. Полиномиальная иерархия

Дата лекции: 15.11.24 Лектор: Зухба Анастасия Викторовна Оператор: Дмитрий Достовалов Редактор: Илья Оплачкин 00:00:00 - Повторение 00:06:40 - Замкнутость P относительно операций 00:08:40 - Замкнутость P относительно A* 00:19:40 - Класс CoNP 00:30:00 - Сертификатное определение 00:47:00 - Полиномиальная иерархия 01:06:10 - Теорема (о существовании алгоритма, решающего задачу поиска) Сайт ВШПИ: https://hsse.mipt.ru