#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на последний в 2024 году логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 18 декабря.
Время проведения семинара 14:30.

МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный

Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16

В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите на почту (kudinov.andrey@gmail.com) заранее.

Заседание пройдет очно без трансляции.

Докладчик: Андрей Кудинов

Название: О сохранение сложности слаботранзитивных модальных логик с универсальной модальностью при добавлении аксиомы связности.

Аннотация.

Под сложностью проблемы выполнимости некоторой модальной логики L понимается сложность следующей массовой задачи: по данной формуле A определить, выполнима ли формула A на некоторой шкале логики L. Эта задача является двойственной к задачи выводимости в логике, т.к. формула A выводима в L тогда и только тогда, когда формула \lnot A невыполнима на L-шкале. Сложностной класс PSPACE содержит все массовые задачи, которые можно решить на машине Тьюринга, которая использует не больше полинома от длины входа ячеек ленты в процессе выполнения.

Мы будем рассматривать слаботранзитивные логики, т.е. логики содержащие wK4 = K + \Box p \land p \to \Box \Box p.
Общезначимость этой логики соответствует тому, что рефлексивное замыкание отношения - транзитивно.
Добавление универсальной модальности увеличивает выразительную силу языка. Добавление универсальной модальности рассматривалось в 90-е годы в работах Горанко и Пасси, а в работе Шехтмана было доказано, что в языке с универсальной модальностью можно выразить связность.

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

➰ ВК