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

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.

Семинар пройдет в среду 20 мая в 14:15.

Адрес:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com

Докладчик: Михаил Рыбаков

Тема:
Сложность логик S1–S8 и их фрагментов.

Аннотация:

Нормальные модальные пропозициональные логики часто PSPACE-трудны (Р.Ладнер и др.), и даже при малом числе переменных в языке. В то же время все расширения таких логик, как K5 или Grz.3, являются coNP-полными. Похожая ситуация наблюдается с ненормальными логиками, содержащимися в K: логики E, EM, EN и многие другие coNP-полны (М.Варди), и то же самое справедливо для их фрагментов от малого числа переменных (А.Кудинов, М.Рыбаков).
Будет рассмотрен вопрос сложности систем S1–S8 (Льюис, Лэндфорд и др.). Две из них — S4 и S5 — являются нормальными и их сложность известна. Остальные являются ненормальными, и похоже, что вопрос их сложности не исследовался. Гипотеза автора состоит в том, что и они, и их фрагменты от одной переменной (а иногда и константные фрагменты) PSPACE-трудны. Почти для всех указанных логик эту гипотезу удалось обосновать. Предполагается представить синтаксическое и семантическое описание этих логик, а также обсудить идеи, лежащие в основе полученных доказательств.