City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Лекция 5. Вычисления с ограничениями по памяти.
Computational Complexity Theory

What: Lecture
When: Tuesday, 12 October 2021, 18:30–19:50
Where: Конференция в zoom, Онлайн
Slides: computationalcomplexity_lecture_121021.pdf

Description

Модель вычислений с ограничениями по памяти. Классы DSpace, NSpace, L, NL, PSPACE, NPSPACE. Граф конфигураций. Теорема Савича. Полнота TQBF в PSPACE.

Video