Ломоносовские чтения 2022: Математическая логика и теория алгоритмов (27.04.2022)

Доклады:
1) О преобразовании протоколов Мерлина–Артура в протоколы Артура–Мерлина. (проф. Н. К. Верещагин.)
Аннотация. Протоколами Мерлина–Артура принято называть вероятностно-проверяемые доказательства с полиномиальными ограничениями на время проверки доказательства (Мерлин посылает Артуру доказательство, которое Артур проверяет, используя бросания монетки). Протоколами Артура–Мерлина называют простейшие интерактивные доказательства (Артур выбирает случайное число, а Мерлин в зависимости от выбранного числа посылает Артуру доказательство). Можно доказать, что любой протокол Мерлина–Артура может быть смоделирован некоторым протоколом Артура–Мерлина. Однако при этом моделировании увеличивается количество использованных случайных битов. В докладе будут приведены свидетельства неизбежности этого.

2) О полноте модальных логик предикатов. (проф. В. Б. Шехтман.)
Аннотация. Около 50 лет назад была обнаружена неполнота семантики шкал Крипке для модальных логик предикатов. Примеров неполноты оказалось значительно больше, чем для пропозиционального случая. В докладе будет дан краткий обзор результатов о полноте и неполноте – в основном, для минимальных предикатных расширений пропозициональных логик. В частности, мы рассмотрим операцию “добавления необходимости” и некоторые логики деревьев.

============================================

Научно-исследовательский семинар
по математической логике
под руководством
академика РАН С. И. Адяна,
академика РАН Л. Д. Беклемишева
и академика РАН А. Л. Семёнова
(по средам в ауд. 16-04 ГЗ МГУ)

Веб-страница семинара:
http://logic.math.msu.ru/sem/nis/

Видео Ломоносовские чтения 2022: Математическая логика и теория алгоритмов (27.04.2022) канала Кафедра матем. логики