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

Таймкоды: 00:00:00 - Введение в лекцию 00:01:19 - Схема, определение и примеры 00:09:00 - Определение SIZE 00:15:45 - Классы P/poly и DTIME(t(n))/a(n) 00:23:27 - Третий подход к P/poly 00:27:20 - Теорема: P строго вложено в P/poly 00:30:41 - Гипотеза: NP не вложена в P/poly 00:34:08 - Теоремы о P/poly 00:37:56 - NC-иерархия 00:46:08 - Вариации определений 00:52:47 - Вложенности классов AС^d и NC^d 00:57:55 - Схемы малой глубины 01:00:00 - Схема для сложения и быстрые сумматоры 01:11:23 - Быстрые мультипликаторы 01:15:10 - Доказательство теоремы EXPSPACE не вложено в P\poly 01:23:07 - Доказательство теоремы Карпа-Липтона 01:29:56 - Доказательство теоремы Мейера 01:39:23 - Что будет дальше Дата лекции: 16.04.26 Лектор: Мусатов Даниил Владимирович Оператор: Ахмедов Али Монтажёр: Трашкун Даниил Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvb2_RW66GZ6P_WkjwR3n9U7 Плейлист