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

Программа

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).

Программа

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

Финансовая поддержка
Курс проводится при финансовой поддержке Минобрнауки России (грант на создание и развитие МЦМУ МИАН, соглашение №  075-15-2022-265).

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