Логический семинар лаборатории им. Манина Высшей школы современной математики

Когда: среда 27 мая, 13:00
Где: МФТИ, Административный корпус, ауд.322,

Доклад:

Михаил Рыбаков,
"Сложность логик S1–S8 и их фрагментов"

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

Будет рассмотрен вопрос сложности систем S1–S8 (Льюис, Лэндфорд и др.). Две из них — S4 и S5 — являются нормальными и их сложность известна. Остальные являются ненормальными, и похоже, что вопрос их сложности не исследовался. Гипотеза автора состоит в том, что и они, и их фрагменты от одной переменной (а иногда и константные фрагменты) PSPACE-трудны. Почти для всех указанных логик эту гипотезу удалось обосновать. Предполагается представить синтаксическое и семантическое описание этих логик, а также обсудить идеи, лежащие в основе полученных доказательств.


Планируется интернет-трансляция по адресу
https://telemost.yandex.ru/j/00084330909943
Регистрируйтесь вашей фамилией, а не псевдонимом!

Страница семинара: https://www.mathnet.ru/rus/conf2559

Адрес: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.
Если у вас нет пропуска МФТИ, то на входе сообщайте, что идёте на наш семинар, и не забудьте паспорт.

#ВШМ_логический