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

Вычисления с ограничениями по памяти
Foundations of computability and complexity theory

What: Lecture
When: Wednesday, 14 November 2012, 18:30–19:50
Where: ПОМИ РАН

Description

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