Формальные языки и сложность вычислений. Лекция 13. Классы L и NL. Задачи PATH и UPATH

Дата лекции: 29.11.24 Лектор: Зухба Анастасия Викторовна Оператор: Дмитрий Достовалов Редактор: Илья Оплачкин 00:00:00 - Повторение 00:09:10 - Эквивалентность определений NL 00:19:40 - Модификации определений 00:29:00 - Задачи PATH и UPATH (Теорема Рейнгольда) 00:41:15 - Схема док-ва, что PATH NL-полный 00:48:30 - Принадлежность дополнение PATH к NL 01:04:50 - Теорема Иммермана-Селепченьи 01:08:35 - 2SAT Сайт ВШПИ: https://hsse.mipt.ru