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

Between P and PSPACE
Kazan / autumn 2015, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Задачи, для которых неизвестно полиномиального по времени алгоритма, вряд ли можно решить на практике. С другой стороны, наличие алгоритма, работающего на полиномиальной памяти, оставляет такую возможность, хотя бы потому, что равенство P=PSPACE не опровергнуто. Между P и PSPACE расположились разнообразные сложностные классы, про которые доказаны интереснейшие теоремы. В этой области сложность вычислений тесно взаимодействует с игровыми моделями. В мини-курсе представлены как классические, так и новые результаты в этой области. Излагается взгляд на возникающие сложностные классы с различных точек зрения.

Примерная программа курса:

  1. Класс PSPACE. Связь с игровыми моделями. Полные задачи: булевы формулы с кванторами, выигрышные позиции в играх с полиномиальным числом ходов;

  2. Полиномиальная иерархия. Разные характеризации уровней иерархии: сертификатное определение, выигрышные позиции в играх с константным числом ходов, альтернирующие машины, вычисления с оракулом;

  3. Задачи подсчёта. Классы #P, PP, связь между ними. Иерархия задач подсчёта (counting hierarchy);

  4. Интерактивные алгоритмы. Распознавание языков при помощи интерактивных алгоритмов: доказывающего и проверяющего. Класс IP. Интерактивные алгоритмы с общими случайными битами и класс AM. Теорема IP=PSPACE;

  5. Рациональные интерактивные доказательства. Интерактивное вычисление функций и распознавание языков с рациональным (т.е. максимизирующим выигрыш) доказывающим. Эквивалентность классу PSPACE для полиномиального числа раундов и иерархии задач подсчёта для константного числа.