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

Лекция 5. Вычисления с малой памятью.
Introduction to Theoretical Computer Science

What: Lecture
When: Monday, 12 October 2020, 18:30–19:50
Where: Конференция в zoom, Онлайн

Description

Множество регулярных языков совпадает с DSpace[1]. DSpace[\(\log \log n\)] содержит нерегулярные языки, а DSpace[\(o(\log \log n)\)]=DSpace[1]. Теорема Савича: Проверить наличие пути в ориентированном графе можно, используя \(\log^2 n\) памяти, PSPACE=NPSPACE.

Video

Other materials

Текущая версия конспекта.