Сложность вычислений 8. Пространственная сложность.

00:00:00 - заставка 00:01:30 - измерение памяти в машинах Тьюринга 00:07:33 - PSPACE, NSPACE и другие 00:13:08 - утверждение 1: L ⊂ P, PSPACE ⊂ EXP 00:18:55 - утверждение 2: NL ⊂ P 00:26:25 - утверждение 3: L ⊂ NL ⊂ P ⊂ NPC ⊂ PH ⊂ PSPACE ⊂ NPSPACE ⊂ EXP ⊂ NEXP ⊂ EXPSPACE ⊂ ... 00:33:08 - теорема Сэвича 00:54:18 - PSPACE-полные задачи, задача TQBF 01:13:03 - обобщённая игра в города (GG) Дата лекции: Лектор: Мусатов Даниил Владимирович Оператор: Порай Екатерина Монтажёр: Хатымов Ренат Плейлист: