Алгоритмические и семантические вопросы математической логики. 2021-2025НИР

Algorithmic and semantic problems of mathematical logic. 2021-2025

Источник финансирования НИР

госбюджет, раздел 0110 (для тем по госзаданию)

Этапы НИР

# Сроки Название
1 1 января 2021 г.-31 декабря 2021 г. Алгоритмические и семантические вопросы математической логики. 2021
Результаты этапа: 1. Получено новое, технически более простое доказательство результата Д.А.Витера о неарифметичности предикатной логики примитивно рекурсивной реализуемости по Салехи. 2. Продолжены исследования расширений исчисления Ламбека с помощью различных операций, в частности итерации и субструктурных модальностей. Доказаны новые результаты о разрешимости и алгоритмической сложности, показывающие, что в практически интересных случаях, когда данные операции применяются к формулам достаточно простой структуры, уровень сложности оказывается намного ниже, чем в общем случае, а в некоторых ситуациях становится возможным разработать эффективные алгоритмы для рассматриваемых логических систем. 3. Будем обозначать через MA[m,a] класс языков, для которых есть двухраундовый протокол Мерлина---Артура, в котором первым посылает сообщение Мерлин, а вторым посылает сообщение Артур, причем длины этих сообщений равны m,a, а вероятность ошибки не превосходит 1/3. Аналогичным образом определяется класс AM[m,a]$ только теперь первым посылает сообщение Мерлин, а не Артур. Хорошо известно, что AM включает MA, а точнее MA[m,a] включено в AM[m,O(ma)]. Это доказывается с помощью амплификации: сначала вероятность ошибки понижается до 2^{-m-1}, при этом количество случайных бит возрастает с a до O(ma), поскольку Артур должен повторять свой алгоритм O(m) раз, используя свежие случайные биты. С помощью случайного блуждания по экспандеру O(ma) можно заменить на a+O(m), доказав тем самым включение MA[m,a] в AM[m,a+O(m)]. Возникает естественный вопрос, можно ли в последнем включении заменить a+O(m) на некоторый многочлен от a. Этот вопрос поставлен в диссертации А.Кнопа. Если MA совпадает с P, то в этом преобразовании случайных битов не нужно вовсе, поэтому ответ на вопрос Кнопа положительный. Поэтому, прежде чем получать отрицательные ответы, нужно доказать, что MA отлично от P, что эквивалентно тому, что P не равно NP (поскольку класс MA включен во второй уровень полиномиальной иерархии). Поэтому современные возможности не позволяют получить отрицательный ответ на этот вопрос. Положительный же ответ представляется маловероятным. В такой ситуации естественно спросить, можно ли построить оракул, относительно которого ответ на этот вопрос отрицательный. Мы построили такой оракул. Точнее, доказано, что относительно некоторого оракула для любых многочленов m,a существует язык в классе MA[m,a], для которого для любого AM [m',a'] протокола выполнено a'(n)>m(n)+a(n)-O(log n) для почти всех n (через n обозначена длина входного слова). Кроме того, мы доказали аналогичную теорему для MA протоколов, в которых Доказывающий никогда не ошибается. А именно, через MAP[m,a] будем обозначать подкласс класса MA[m,a], состоящих из тех языков, для которых есть протокол, в котором для слов из языка вероятность ошибки равна нулю. Из теоремы Гача --- Сипсера --- Лаутемана о включении BPP во второй класс полиномиальной иерархии следует, что MAP=MA, а точнее, класс MA[m,a] включен в MAP[O(ma),O(a^2)]. Поэтому из доказанной теоремы следует, что относительно некоторого оракула, AM протоколам, моделирующим MAP[m,a] протоколы, недостаточно poly(a) случайных битов. Мы доказываем более точные оценки: относительно некоторого оракула, для любых многочленов m,a существует язык в MAP[m,a], для которого для любого AM протокола выполнено a'(n)>max{m(n),a(n)}-O(log n) для почти всех n (отличие от MA протоколов в том, что m(n)+a(n) заменено на max{m(n),a(n)}. 4. Мы проанализировали сеть, состоящую из двух открытых каналов, ведущих к двум потребителям, нуждающимся в некоторой информации y,z, и уже обладающим какой-то другой информацией x,w. Здесь x,y,z,w – слова над двоичным алфавитом. Мы интересовались, чему равно минимально возможное разглашение (то есть количество информации по Колмогорову об x,y,z,w, которое узнает посторонний наблюдатель, прослушивающий каналы), а также минимально возможное разглашение информации об x,w. А также тем, можно ли одновременно достигнуть этого минимального разглашения и минимизировать длины сообщений, передаваемых по каналам. Нам удалось решить поставленные задачи для двух частных случаев: (а) y=z и (б) x=w. В случае (а) минимально возможное разглашение информации о четверке x,y,z,w было по существу найдено Ан.Мучником (оно равно максимуму из условной сложности y при известном x и условной сложности z при известном w). Мы установили, что минимально возможное разглашение информации о паре x,w равно max{I(z:w|x), I(z:x|w)}. При этом оба минимума могут быть достигнуты одновременно с минимумом длин передаваемых по каналам сообщений. В случае (б) ситуация более сложная. Очевидно, что минимально возможное разглашение информации о четверке x,y,z,w равно максимуму из чисел C(y|x),C(z|x),C(y,z|x), а минимально возможное разглашение информации о паре x,w равно нулю. Однако ни один из этих минимумов не может быть достигнут одновременно с минимумом длин передаваемых по каналам сообщений (в этом и состоит наш главный результат).
2 1 января 2022 г.-31 декабря 2022 г. Алгоритмические и семантические вопросы математической логики. 2022
Результаты этапа: 1. Найдено минимально возможное разглашение информации при некоторых задачах о передаче информации через открытые каналы. 2. Построено предикатное исчисление, которое может служить логической основой для конструктивной арифметики Маркова. 3. Доказана алгоритмическая неразрешимость для двух расширений некоммутативного исчисления Ламбека субэкспоненциальными модальностями. Определён класс сложности коммутативной логики действий с индуктивной аксиоматизацией итерации. 4. Построено новое континуальное семейство модальных предикатных логик, неполных в семантике Крипке. Это семейство состоит из минимальных предикатных расширений логик, полученных добавлением необходимости к расширениям модальной логики Т.
3 1 января 2023 г.-31 декабря 2023 г. Алгоритмические и семантические вопросы математической логики. 2023
Результаты этапа: 1. Доказано, что полудуплексная сложность с противником некоторой частичной функции строго меньше классической коммуникационной сложности той же функции, причем разница между ними имеет порядка логарифма от этих величин. 2. Доказано, что схемы аксиом свёртки и выбора в арифметике Пеано 2-го порядка не выводятся из их беспараметрических подсхем. 3. Доказана алгоритмическая неразрешимость семантического следования из условий коммутативности на классе всех алгебр Клини.
4 1 января 2024 г.-31 декабря 2024 г. Алгоритмические и семантические вопросы математической логики. 2024
Результаты этапа:
5 1 января 2025 г.-31 декабря 2025 г. Алгоритмические и семантические вопросы математической логики. 2025
Результаты этапа:

Прикрепленные к НИР результаты

Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".