Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Лекция 5. Вычисления с ограничениями по памяти.
Теория сложности вычислений

Что: Лекция
Когда: Вторник, 12 октября 2021, 18:30–19:50
Где: Конференция в zoom, Онлайн
Слайды: computationalcomplexity_lecture_121021.pdf

Описание

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

Видео