Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

Между P и PSPACE
Осень 2015, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

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

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

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

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

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

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