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

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

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

Описание

Класс TISP[t(n),s(n)]. Теорема о том, что NTime[n] не содержится в TISP[n^{1.2}, n^{0.2}] и следствие из нее. Теорема Карпа-Липтона, теорема о существовании функции большой схемной сложности, теорема Каннана и следствие из нее. Вычисление с неравномерной подсказкой.

Видео