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

Вычисления с ограничениями по памяти
Основы вычислимости и теории сложности

Что: Лекция
Когда: Среда, 14 ноября 2012, 18:30–19:50
Где: ПОМИ РАН

Описание

Теорма Савича и следствие о NPSPACE = PSPACE. Полнота TQBF в классе PSPACE. Теорема об иерархии по памяти. Логарифмические по памяти сведения и их свойства. Класс NL, полная задача в нем.