В курсе мы сделаем краткое введение в теорию сложности и неклассические логики. Далее мы докажем все основные результаты о сложности неклассических логик, среди которых встречаются как и относительно несложные логики, так и очень сложные, вплоть до неразрешимых.

Программа

1. Введение в теорию алгоритмической сложности (понятие сложностных классов с ограничениями по времени и по памяти). Пример неразрешимой задачи.
2. Сложностные классы $P, NP, coNP, PSPACE, EXPTIME$ и другие. Их взаимосвязь.
3. Полные задачи для классов сложности. Классические примеры полных задач: замощения, выполнимость формул и т.д.
4. Краткое введение в интуиционистскую и модальную логику, семантика Крипке.
5. Доказательство того, что логика $S5$ $coNP$ полна.
6. Доказательство того, что логики $Int, K, K4, S4$ $PSPACE$ полны.
7. Пример неразрешимой логики с несколькими модальностями.
8. Добавление универсальной модальности и транзитивного замыкания и влияние этого на сложность логик.
9. Соединение логик и их сложность.
10. Произведения модальных логик. Сложность произведений. Сложность логик $S5 \times S5$ и $K \times K$.
11. Неразрешимость $K4 \times K4$ и $S5 \times S5 \times S5$.
12. Ненормальные модальные логики. Окрестностная семантика. Сложность ненормальных модальных логик $E, EM, EC$.

Литература
[1] В.Н. Крупский, Введение в сложность вычислений. Москва: Факториал, 2006.
[2] A. Kurucz, F. Wolter, M. Zakharyaschev, Dov M. Gabbay, Many-Dimensional Modal Logics: Theory and Applications, Vol. 148, Elsevier, 2003.
[3] M. Marx, Complexity of Modal Logic. Chapter 3, in: Handbook of Modal Logic, Elsevier, 2006, Editors: P. Blackburn, J. F.A.K. van Benthem, F. Wolter.
[4] E. Spaan, Complexity of Modal Logics. Doctoral thesis, University of Amsterdam (2016).

Лектор
Кудинов Андрей Валерьевич

Организации
Математический институт им. В.А. Стеклова Российской академии наук, г. Москва
Математический центр мирового уровня «Математический институт им. В.А. Стеклова Российской академии наук» (МЦМУ МИАН)