Аннотация результатов, полученных в 2020 году
Исследовано применение метода символического пфаффиана для задачи подсчета числа совершенных паросочетаний в графе. Установлена связь между трудоемкостью этого метода и сложностью функции знака паросочетания в модели обобщенных разрешающих деревьев. Для общего случая получены высокие нижние оценки этой сложности. Эти оценки получены применением методов коммуникационной сложности. Данные результаты показывают связь между быстрыми алгоритмами решения трудных комбинаторных задач и сложностью булевых функций в слабых моделях вычисления. Исследованы автоматы с дополнительной структурой данных (Д.С.Д.) – конечные автоматы, к которым добавили структуру данных. Широко известны автоматы со стеком (магазинные автоматы), которые используются в компиляторах — это важный частный случай нашей модели. Получены структурные результаты об этой общей модели и результаты в области сложности вычислений. Основной результат — проблема непустоты языка, распознаваемого недетерминированным автоматом с Д.С.Д. равносильна (по вычислительной сложности) задаче о проверке принадлежности слова языку, распознаваемому недетерминированной машиной Тьюринга с логарифмической памяти с добавленной к ней (той же самой) Д.С.Д. Изучались свойства коммуникационных протоколов, которые позволяют двум участникам получить общий секретный ключ при условии, что связь между ними осуществляется по открытому канал. Предполагается, что участникам протокола даны коррелированные исходные данные x и y соответственно. Известно, что оптимальный размер секретного ключа, который могут получить участники такого протокола, равен взаимной информации между x и y. Мы показали, что коммуникационная сложность такого протокола (в худшем случае) равна колмогоровской сложности x относительно y. Более того, коммуникационная сложность задачи не уменьшается, даже если участники выбирают секретный ключ много меньшего (но не пренебрежимо малого) размера. Л. Левиным было предпринято четыре попытки перенести определение понятие количества взаимной информации на случай бесконечных последовательностей. Наиболее естественным и технически простым из этих определений является первое, данное в статье в ППИ в 1974 году. В этой статье утверждается, что для этого определения выполнены законы сохранения информации, однако доказательство в статье отсутствует. Позднее несколькими авторами были найдено и опубликовано доказательство первого из двух законов. Однако доказательство второго закона (сохранение информации при приписывании шума) оставалось неопубликованным. Нами найдено такое доказательство. Кванторная задача удовлетворения ограничениям это обобщение обычной задачи удовлетворения ограничениям, где помимо кванторов существования допускаются кванторы всеобщности. Ранее было показано, что для разных языков ограничений эта задача может либо решаться за полиномиальное время, либо быть NP-полной, PSpace-полной, coNP-полной, или даже DP-полной и Θ2P-полной. Тем не менее нам удалось показать, что на трех-элементном множестве эта задача либо NP-полна, либо coNP-полна, либо PSpaсe-полна, либо решается за полиномиальное время. Также мы обобщили идею сильных подалгебр, появившуюся в доказательстве Д.Н.Жука классификации сложности задачи удовлетворения ограничениям (известном как CSP Dichotomy Conjecture). Мы показали, что любая идемпотентная алгебра содержит подалгебру с дополнительными сильными свойствами и получили простое и естественное доказательство многих известных алгебраических фактов, а также фактов о сложности задачи удовлетворения ограничениям. Мы определили новый способ определения колмогоровской сложности для частного случая теоремы Слепяна-Вольфа, названный «характеризацией информационного расстояния». Задача состоит в том, чтобы для данной пары (x, y) построить программу, которая отображает слово x в слово y и слово y в слово x. Мы доказали, что минимальная длина такой программы не обладает свойством метрики, и обнаружили ошибки в существующих опубликованных доказательствах, которые утверждают обратное. Удивительно, но когда мы ограничиваемся сложными строками, сложности которых отличаются от максимально возможной на логарифмическую величину, расстояние действительно является метрикой (для подходящей машины). Исследовался вопрос о сильных нижних оценках сложности булевых схем в модели разрешающих деревьев с запросами, зависящими от не более чем двух переменных функции. Доказана сильная нижняя оценка сложности функции голосования в этой модели. В исследованиях разрешимость по Нэшу позиционных игр n лиц на симметрических ориентированных графах получены достаточные условия разрешимости по Нэшу в чистых стационарных для позиционных игр n лиц, моделируемых симметрическими ориентируемыми графами. В случае n=2 (два игрока) получены достаточные условия равномерной разрешимости по Нэшу. В исследованиях потоков в ориентированных взвешенных графах предложен алгоритм вычисления и доказана единственность сбалансированного потока в анизотропной (полупроводниковой) сети, моделируемой ориентированным графом, что обобщает результат 1984-го года для симметрических (изотропных) ориентированных графов. Был придуман алгоритм для следующей задачи. Дан многочлен в виде алгебраической схемы глубины 4, вида P_1 + P_2 + P_3. где все P_i = l_{i1} *...*{l_ik}, где все l_{ij} есть многочлены от нескольких переменных степени два, то есть квадратичные формы. Требуется узнать, равняется ли данный многочлен нулю тождественно. Мы предъявили детерминированный полиномиальный алгоритм для решения этой задачи в случае, если известно, что все идеалы <l_{ik}, l_[js}> являются простыми (детерминированного полиномиального алгоритма для решения данной задачи в общем случае неизвестно).

Аннотация результатов, полученных в 2021 году
Хорошо известно, что MA (протоколы Мерлина — Артура) включено в AM (протоколы Артура - Мерлина). Стандартное преобразование MA протокола, в котором количество случайных бит Артура равно a, а длина сообщения Мерлина равна m, требует O(ma) случайных бит в AM протоколе. В диссертации A. Кнопа был поставлен вопрос, можно ли O(ma) заменить на некоторый многочлен только от a. Мы доказали, что относительно некоторого оракула это преобразование требует не менее m+a случайных бит в AM протоколе. Проанализирована сеть, состоящая из двух открытых каналов, ведущих к двум потребителям, нуждающимся в некоторой информации y,z, и уже обладающим какой-то другой информацией x,w, с точки зрения минимизации разглашения информации об x,y,z,w. Получен линейный алгоритм (в RAM-модели) симуляции детерминированных d-ограниченных автоматов. Получена новая формализация конечных автоматов с дополнительной структурой данных (ДСД), которая покрывает такие модели как магазинный автомат и автомат со словарём (и многие другие); в рамках модели были получены результаты об эквивалентности (по сложности вычислений) базовых задач и языков, распознаваемых недетерминированными машинами Тьюринга на логарифмической памяти с ДСД; доказана PSPACE-полнота проблемы пустоты для автомата с ограниченным словарём (добавление ровно одного слова) Для перспективной модели вычислений — автоматов со словарём — получены результаты о представлении таких автоматов в нормальных формах специального вида. Эти нормальные формы фиксируют синтаксические свойства автоматов со словарём и упрощают анализ свойств в этой модели. Получены новые варианты нормальных форм как для детерминированных, так и для недетерминированых автоматов со словарём. Предложена гипотеза полулинейности для игр вычитания с неотрицательными векторами разностей. Доказано, что из нее следуют как существование полиномиальных алгоритмов решения, так и разрешимость проблемы эквивалентности таких игр. Нам удалось показать, что задача «Нет радуги» является NP-полной, тем самым закрыть самый известный вопрос о сложности сюръективной задачи удовлетворения ограничениям. Кроме этого мы опровергли гипотезу Чена о сложности сюръективной задачи удовлетворения ограничениям и показали, что сложность этой задачи в принципе не может быть описана в терминах полиморфизмов, а значит нужны совершенно новые идеи для полного решения задачи. Также нам удалось доказать, что кванторная задача удовлетворения ограничениям относительно предиката (x=y->y=z) на бесконечном множестве является PSpace-полной, что позволило завершить классификацию сложности этой задачи для любого языка ограничений, задаваемого булевыми комбинациями равенств. Колмогоровская сложность слова, возможно, является наиболее фундаментальным способом измерения информации в строке и определяется как минимальная длина программы, вычисляющей строку. Точно так же алгоритмическое информационное расстояние между строками x и y задается минимальной длиной программы, которая отображает x в y и отображает y в x на беспрефиксной машине Тьюринга. В приложениях машинного обучения вместо этого используются оценки max {K (x | y), K (y | x)}, и известно, что расстояние равно этому значению с точностью O (log K (x, y)). Мы доказали, что это выполняется с оптимальной точностью O (1), если расстояние не меньше логарифмического минимума из длин x и y. Мы исследовали применимость классических псевдослучайных генераторов для построения графов с хорошими спектральными свойствами (так называемых экспандеров). Мы показали, что в любом плотном кластере, состоящем из слов с достаточно малыми попарными информационными расстояниями (информационное расстояние определяется в смысле колмогоровской сложности), можно выделить общую информацию, содержащуюся во всех элементах данного кластера. Исследовались оценки для булевых схем, вычисляющих функцию голосования, и состоящих из функций голосования меньшего числа переменных. Доказаны верхние оценки на входную степень элементов таких схем фиксированной постоянной глубины. Обобщённая задача о рюкзаке заключается в следующем. Даны n предметов с их стоимостями c_1, c_2, ...., c_n, объёмами V_1, ...., V_n, цены на их хранения d_1,...., d_n. а также объём рюкзака V. Разрешается сдать некоторые вещи на хранения, после чего приходит вор с рюкзаком объёма V и берёт вещи, не сданные на хранения. Спрашивается, какие вещи стоит сдать на хранение, чтобы общая стоимость потерь была наименьшей? Мы придумали полиномиальный алгоритм, который решает эту задачу приближенно.

Аннотация результатов, полученных в 2022 году
Одно из важных направлений современной теоретической информатики является дерандомизация, то есть, сокращение количества случайных битов, использующихся алгоритмами. В этой области интересны как положительные результаты, так и отрицательные. Нам удалось установить некоторый отрицательный результат. А именно мы установили, что при любом преобразовании протоколов Мерлина – Артура в протоколы Артура – Мерлина полученный протокол по всей видимости требует существенно большего количества случайных битов, чем исходный протокол. Тем самым мы показали, что гипотеза А. Кнопа маловероятна. Следующие результаты, давно известные для случая неориентированных (иными словами, ориентированных симметрических) графов обобщены на случай произвольных ориентированных графов: - Полиномиальный алгоритм построения сбалансированного потока для многополюсной задачи транспортировки. - Доказательство неравенства треугольника для обобщенных пространств сопротивлений. Сформулированы две новые гипотезы о разрешимости по Нэшу позиционных игр и получены частичные результаты. Показано, что кванторная задача удовлетворения ограничениям для произвольного языка ограничений на конечном множестве либо является PSpace-трудной, либо относится к классу Pi_2^P. Доказано, что в случае Pi_2^P для любой невыполнимой формулы существует полиномиальная выигрышная стратегия для игрока, играющего за квантор всеобщности. Получено простое и более общее доказательство сведения кванторной задачи удовлетворения ограничениям к обычной задаче удовлетворения ограничениям в случае, когда множество полиморфизмов языка ограничений обладает полиномиальной степенью роста. Построен язык ограничений на 6-элементном множестве, для которого кванторная задача удовлетворения ограничениям является Pi_2^P-полной. Построены языки ограничений на двухэлементном множестве, для которых задача удовлетворения ограничениям с обещаниями может быть решена сведением к обычной задаче удовлетворения ограничениям на множестве размером p, при этом это значение p не может быть уменьшено. Изучены общие модели вычислений: 1-сторонние и 2-сторонние автоматы и машины Тьюринга, работающие на логарифмической памяти, и снабженные дополнительной структурой данных (ADS), которая определяется языком протоколов работы с этой структурой. Для таких 1-сторонних автоматов проблема непустоты оказывается эквивалентной задаче регулярной реализумемости для языка протоколов с точностью до сводимостей на логарифмической памяти. Задача регулярной реализуемости состоит в проверке непустоты пересечения регулярного языка (входа задачи) и языка протоколов. Доказана универсальность задач регулярной реализуемости для языков протоколов. Проблема коммутации сетей берет свое начало в старых телефонных сетях. Изначально, когда телефон был только у нескольких человек в деревне, все телефоны были попарно соединены проводом. Однако по мере того, как все больше людей начали использовать телефоны, такое квадратичное количество проводов стало невозможным, и были введены коммутационные станции. Цель состоит в том, чтобы свести к минимуму общее количество проводов, но так, чтобы любой набор соединений мог реализовываться одновременно. Причем такие сети должны быть неблокирующими, а это значит, что запросы на подключение могут поступать в любой момент, а позже могут быть разблокированы. В настоящее время эта область исследований имеет множество применений в интернет-маршрутизации и структурировании электронных компонентов. Оптимальное решение проблемы было найдено в 90-х годах. Однако длина соединения в этих решениях неограничена. N-коннекторы постоянной глубины с минимальным количеством ребер были введены в [Friedman, Feldman, Pippenger, 1988], но алгоритм маршрутизации работает за время, экспоненциальное по N. Несмотря на многочисленные исследования, алгоритмы с полиномиальным временем были найдены только для постоянной глубины с огромным количеством ребер. В результате нашего исследования алгоритмов динамического двумерного сопоставления мы смогли решить эту проблему. Для каждого k мы построили N-соединитель глубины k с полилогарифмическим временем. Таким образом, для оптимальных размеров время намного лучше, чем можно было бы ожидать, и наблюдается двойное экспоненциальное улучшение по сравнению с лучшим известным временем! Исследована коммуникационная сложность протокола обмена секретными ключами в теоретико-информационной постановке для входов заданным хэмминговским расстоянием. Изучены конструкции псевдослучайных графов Шрайера, обладающие свойствами экспандера. Показано, что каждое линейное неравенство, верное для колмогоровской сложности или энтропий, также верно для колмогоровских сложностей с полиномиальным ограничением на используемую память. В работах Аллендера и других авторов была предложена идея использовать оракул R, состоящий из слов большой колмогоровской сложности. Мы доказываем новые результаты в этом направлении. Одним из наших результатов является следующая теорема: Показано, что класс языков разрешимых на вероятностной машине Тьюринга за полиномиальное время с неадаптивным использованием оракула R является подмножеством класса языков из экспоненциальной иерархии. Получены результаты о связи проблемы принадлежности для детерминированной версии конечных автоматов с дополнительной структурой данных (ДСД) и детерминированной задачи регулярной реализуемости для языка протоколов структуры данных, а также связь последней и детерминированной машины Тьюринга на логарифмической памяти с дополнительной структурой данных. Эти результаты продолжают полученную ранее сложностную версию известных результатов о разрешимости задач связанных с конечными автоматами (с другим обобщением) ДСД, полученных Дж Хопкрофтом и Дж. Ульманом. Исследовались сортирующие сети небольшой глубины. Для произвольной постоянной глубины были доказаны нетривиальные верхние и нижние оценки арности компараторов, для которых такие сети существуют.