Между P и PSPACE

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

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

• Класс PSPACE. Связь с игровыми моделями. Полные задачи: булевы формулы с кванторами, выигрышные позиции в играх с полиномиальным числом ходов;
• Полиномиальная иерархия. Разные характеризации уровней иерархии: сертификатное определение, выигрышные позиции в играх с константным числом ходов, альтернирующие машины, вычисления с оракулом;
• Задачи подсчёта. Классы #P, PP, связь между ними. Иерархия задач подсчёта (counting hierarchy);
• Интерактивные алгоритмы. Распознавание языков при помощи интерактивных алгоритмов: доказывающего и проверяющего. Класс IP. Интерактивные алгоритмы с общими случайными битами и класс AM. Теорема IP=PSPACE;
• Рациональные интерактивные доказательства. Интерактивное вычисление функций и распознавание языков с рациональным (т.е. максимизирующим выигрыш) доказывающим. Эквивалентность классу PSPACE для полиномиального числа раундов и иерархии задач подсчёта для константного числа.