Сложность вычислений 10. Теорема Иммермана-Селепченьи. Схемная сложность

Описание: Таймкоды:
00:00:00 - Организационная информация
00:01:04 - Теорема Иммермана-Селепченьи
00:07:10 - Сертификатное определение NL
00:16:50 - Сертификат недостежимости
00:42:11 - Вайбово стирает с доски
00:42:47 - Задача 2SAT
00:57:37 - Схемная сложность
01:04:50 - Схема для XOR
01:07:55 - 3 определения схем
01:19:08 - клиффхенгер

Дата лекции: 12.11.2025

Лектор: Мусатов Даниил Владимирович

Оператор: Козырь Екатерина
Монтажёр: Крещик Владимир

Плейлист на YouTube:    • Сложность вычислений (3 курс, осень 2025) ...  
Плейлист в ВК: https://vkvideo.ru/playlist/-20607802...