Появилась видеозапись конференции "Ломоносовские чтения - 2022" от 27.04.2022

Были прочитаны доклады:

О преобразовании протоколов Мерлина–Артура в протоколы Артура–Мерлина.

Докладчик: проф. Н. К. Верещагин.

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

О полноте модальных логик предикатов.

Докладчик: проф. В. Б. Шехтман.

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

Источник: vk.com

Комментарии: