3 июня в 18:10 состоится заседание научно-исследовательского семинара «С логической точки зрения» («From the Logical Point of View»).

А.В. Кудинов
НИУ ВШЭ

выступит с докладом
«Логика SSL и ее сложность»

Аннотация

Доклад посвящён логике подмножеств пространства (Subset Space Logic, SSL) — бимодальной эпистемической логике с одной модальностью знания (K) и второй модальностью (\Box), соответствующей тому, что агент потратил какие-то ресурсы, чтобы увеличить свои знания. Вторую модальность можно воспринимать, как некоторую динамику, поэтому SSL можно отнести к динамической эпистемической логике.

Логика была введена в работе A. Dabrowski, L. S. Moss & R. Parikh «Topological reasoning and the logic of knowledge» (Annals of Pure and Applied Logic, 1996), где, в частности, были предложены её аксиоматизации для класса всех подмножеств и для класса топологических пространств. В работе была доказана финитная аппроксимируемость, дающая оценку сверху на сложность логики SSL, а именно, что SSL лежит в 2EXPTIME. Также очевидно, что SSL - PSPACE-трудна, т.к. в нее погружается логика S4. Более точные оценки долгое время были неизвестны.

В работе 2021 года (препринт был в 2019) Гертлингом и Кроммесом (Hertling, Krommes) было доказано, что SSL является EXPSPACE-полной.

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

Все нужные определения и понятия будут даны, предварительные знания о сложности не требуются, но приветствуются.
https://llfp.hse.ru/announcements/1164883547.html