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

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