Сложность вычислений 9. Вычисления на логарифмической памяти

00:00:00 - заставка 00:01:07 - задачи из L про скобочные последовательности (PAR, PARBRA) 00:11:20 - двоичная арифметика 00:24:17 - теорема Рейнгольда и её следствия (UPATH, UCONN, ACYCLIC) 00:32:53 - TREE за логарифм памяти 00:39:02 - чёрная полоса в жизни записи этой лекции 00:41:32 - NL-полная задача, логарифмическая сводимость и вычислимость 00:58:30 - альтернативное определение NL через сертификаты 01:05:20 - теорема Иммермана-Селепченьи (NL = coNL) Дата лекции: Лектор: Мусатов Даниил Владимирович Оператор: Порай Екатерина Монтажёр: Хатымов Ренат Плейлист: