#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 427 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.

Дата и время: 09.10.2026 в 16:20

Докладчик: Никита Лукашов (аспирант, НИУ ВШЭ)

Название доклада:

Название: Сложность модальных логик (часть 1)

Аннотация:

Планируется два доклада, рассказ которых будет посвящён исследованию разрешимости и вычислительной сложности нормальных модальных логик.

В первом докладе мы рассмотрим различные методы доказательства разрешимости для логик, обладающих свойством конечных моделей. Будет показано, что наличие этого свойства само по себе не гарантирует существование эффективных алгоритмов: будет приведена конструкция несчётного семейства даже полиномиально аппроксимируемых логик с неразрешимой проблемой принадлежности. Затем мы обсудим различные семантические и синтаксические ограничения, при наложении которых удаётся установить разрешимость в целом, без оценки требуемых вычислительных ресурсов.

Во втором докладе мы сосредоточимся на границах сложности. После краткого напоминания классов P, NP и PSPACE будет изложен общий метод установления NP-полноты для нормальных модальных логик и, в частности, продемонстрировано, что логика S5 является таковой. Затем будет приведена общая конструкция, показывающая, что такие модальные логики, как K, K4, S4 и GL, не являются полиномиально аппроксимируемыми, что будет означать необходимость принципиально иных подходов к установлению их принадлежности к PSPACE. В заключение, используя приведённую конструкцию для задачи TQBF, мы также воспроизведем доказательство классической теоремы Р. Ладнера (1979), утверждающей, что любая нормальная модальная логика в интервале между K и S4 является PSPACE-трудной

Список литературы:
[1] Blackburn P., De Rijke M., Venema Y. Modal logic: graph. Darst. – Cambridge University Press, 2001. – Т. 53.
[2] Ladner R. E. The computational complexity of provability in systems of modal propositional logic //SIAM journal on computing. – 1977. – Т. 6. – №. 3. – С. 467-480.