Сложность вычислений 11. Схемная сложность

Таймкоды: 00:00:00 - Напоминание про схем из функциональных элементов 00:06:50 - Теорема Лупанова и Шеннона (б/д) 00:09:53 - P/poly. Разные определения 00:16:40 - Класс P/1 00:20:30 - Эквивалентность определений 00:26:40 - P лежит в P/poly 00:27:40 - EXPSPACE не лежит в P/poly 00:35:00 - Связь с NP 00:38:00 - Теорема Карпа-Липтона 00:45:23 - Теорема Мейера 00:51:55 - Схемы малой глубины 01:10:25 - Быстрые сумматоры Дата лекции: 19.11.2025 Лектор: Мусатов Даниил Владимирович Оператор: Козырь Екатерина Монтажёр: Крещик Владимир Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvbboj4ZMEucHSR5p9ysMODF Плейлист