Сложность определений и сложность вычисленийНИР

Computational complexity and descriptive complexity

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

грант РФФИ

Этапы НИР

# Сроки Название
1 1 декабря 2016 г.-31 декабря 2016 г. Сложность определений и сложность вычислений, этап 1
Результаты этапа:
2 1 января 2017 г.-31 декабря 2017 г. Сложность определений и сложность вычислений, этап 2
Результаты этапа: (Верещагин, Милованов) Алгоритмическая статистика с ограничением на ресурсы. Предложена три определения правдоподобности гипотезы для алгоритмической статистики с ограничением времени, которые мы называются приемлемостью, правдоподобностью и оптимальностью. Грубо говоря, приемлемость гипотезы P, как объяснения для x, означает, что x обладает всеми простыми и быстро проверяемыми свойствами, которыми обладают почти все объекты относительно распределения P. В определении правдоподобности мы требуем того же и для сложных быстро проверяемых свойств, однако усиливаем требования к понятию ``почти все'' в зависимости от того, насколько сложным является свойство. Наконец, в определении оптимальности мы просто требуем, чтобы P(x) было достаточно большим (не меньше, чем два в степени минус колмогоровская сложность x с полиномиальным ограничением времени). Все результаты в этом разделе получены при некоторых правдоподобных теоретико-сложностных предположениях. Основной результат утверждает, что для приемлемости и правдоподобности существуют нестохастические слова, то есть, слова, не имеющие простых приемлемых (правдоподобных) объяснений. Также установленно, что бывают слова, у которых есть простые приемлемые, но неправдоподобные и неоптимальные гипотезы. Наши результаты продолжают работам по Колмогоровской сложности с ограничением на ресурсы, написанные Fortnow, Allender и другими. В частности в их работах изучался вопрос о разнице между сложностью различения и сложностью порождения с полиномиальным ограничением на ресурсы. Наша техника позволила позволила получить новый результат для решения этого вопроса. А именно, мы использованы комбинаторные методы и различные генераторы псевдослучайных чисел (Нисана-Вигдерсона, криптографические). (Мусатов) Вероятностные и колмогоровские экстракторы. При помощи конструкции Синя Ли вероятностного экстрактора для трёх источников получена теорема о существовании колмогоровских экстракторов с тремя источниками для полиномиальных ограничений на время. При этом три источника должны быть мало зависимы друг от друга в смысле недетерминированной сложности CN. Мы использовали теоремы об эквивалентности вероятностных и колмогоровских экстракторов, получены в 2009-11 гг. в работах Фортноу, Хичкока и др. Однако точности этих теорем не хватает для автоматического преобразования полученных позднее вероятностных экстракторов в колмогоровские и, как следствие, в колмогоровские экстракторы с ограничением на ресурсы. Конструкция для ограничения на память получена автором в 2012 г. Наш результат представляет первую успешную конструкцию с ограничением на время. (Козачинский) Получены почти что совпадающие нижние и верхние оценки вероятностной коммуникационной сложности задачи Gap Hamming Distance, GHD_{L, U} (задачи отделения L-близких по Хеммингу пар слов от U-далеких) c односторонней ошибкой. А именно, доказана нижняя оценка \Omega(L^2/U) и верхняя оценка O(L^2/U \log L). Коммуникационная сложность задачи Gap Hamming Distance изучалась, начиная с работы Indyk и Woodruff (2003), в связи с ее многочисленными приложениями для получения нижних оценок в теории потоковых алгоритмов и в теории тестирования свойств. Версия этой задачи с односторонней ошибкой также находила свои применения (например, в работе Blais, Brody, Matulef 2011 года). Тем не менее, для этой версии мало что было известно о сложности GHD_{L, U} в общем случае. А именно, была известна верхняя оценка вида O(L\log n), не зависящая от L, а также нижняя оценка \Omega(U) для случая, когда U не более в константу раз превышает L (Buhrman, Cleve, Wigderson, 1998). Для задачи Gap Hamming Distance был разработан новый вероятностный метод доказательства отдаленности двух слов по Хеммингу, основанный на неравенстве треугольника. Также для версии этой задачи с односторонней ошибки была адаптирована техника понижения размерности входа из работы Huang, Shi, Zhang, Zhu (2006). (Подольский) Построен пример булевой функции, вероятностная коммуникационная сложность которой не убывает с ростом числа игроков большего логарифма от размера входа и с точностью до константы равна логарифму от размера входа каждого из игроков. Ранее исследовался вопрос о вероятностной коммуникационной сложности обобщенного скалярного произведения и дизъюнктности множеств в модели "число на лбу" для случая сверхлогарифмического по размеру входа числа игроков. В прошлом году было показано, что вероятностая коммуникационная сложность этих функций убывает в ростом числа игроков и становится константой, когда число игроков полиномиально по размеру входа каждого из них. В этом году построен пример функции, вероятностная коммуникационная сложность которой не убывает с ростом числа игроков большего логарифма от размера входа и с точностью до константы равна логарифму от размера входа каждого из игроков. Исследование коммуникационной сложности для большого числа игроков является важным направлением в области сложности вычислений. Ранее примера функции, для которой сложность не меняется с ростом числа игроков, известно не было. Для доказательства результатов о коммуникационной сложности функций для большого числа игроков использовалась стандартная для этой области техника: комбинаторные и вероятностные методы, приближение булевых функций многочленами. Доказано (М.Н. Вялый, А.А. Рубцов), что языки, распознаваемые детерминированными автоматами со словарём (Deterministic Set Automata) –– подклас класса P, а недетерминированные –– подкласс класса NP. Для каждой модели приведены примеры полных языков. Доказано, что проблема принадлежности слова языку для детерминированных автоматов со словарём лежит в классе P. Получено, что проблема пустоты для детерминированных и недетерминированных автоматов со словарём PSPACE-трудна, а в случае унарного алфавита словаря NP-трудна. сследование автоматов с добавленной структурой данных является классическим вопросом теории формальных языков. Исследуемая модель была представлена М.Кутрибом, А. Мальхером и М. Вендландтом в 2014 году, вызвала интерес у учёных в сфере формальных языков. Авторы модели получили структурные результаты и результаты о разрешимости, вопросы о сложности основных вычислительных задач для данной модели оставался открытым до этой работы. Использована техника рациональных конусов, разработанная в (первую очередь в) области КС-языков французской и американской школой в 60-х годах XX века. Основным и оригинальным приёмом является формализация понятия протокола работы модели вычислений через формальный язык, что позволило получить связь с задачей регулярной реализуемости и использовать наработанную в ней технику. Также была развита техника нормальных форм автоматов со словарём, изобретённая авторами модели. (Ромащенко) Используя методы дерандомизации, мы построили в работе [1] новые типы экспандерных кодов, имеющих приложения в теории сложности доказательств. А именно, с помощью данных кодов мы описали булевы формулы, выполнимость которых трудно проверить с помощью алгоритмов из некоторого широкого класса SAT-солверов (алгоритмов, проверяющих выполнимость булевых формул). Хотя задача проверки выполнимости булевой формулы в общем виде является NP-полной, известны различные типы алгоритмов (SAT-солверов), которые на практике для многих типов формул находят решение за субэкспоненциальное время. В частности, интересным направлением исследований являются алгоритмы, использующие представление формул в виде так называемых OBDD (ordered binary decision diagram, упорядоченных двоичных диаграмм разрешения). Данные типы алгоритмов восходят в работе Atserias, Kolaitis и Vardi (2004). В данной работе мы рассмотрели широкий класс OBDD-алгоритмов -- алгоритмы, допускающие при обработке OBDD-диаграмм операцию элиминиации квантора и операцию произвольного переупорядочивания пропозициональных переменных. Мы показали, что для построенных нами булевых формул все алгоритмы данного типа требуют времени, экспоненциально зависящего от длины формулы. Таким образом, найдены естественные примеры задач, на которых алгоритмы данного класса не могут быть эффективны. В данной работы мы использовали конструкции, использующие блуждание на спектральных экспандерах. В сочетании с методами теории кодирования (коды с декодированием списком) данная техника позволила нам построить коды с некоторыми неконвенциональными комбинаторными свойствами, необходимыми для применений в теории сложности доказательств. (Артамонов) Было найдено эффективное решение для задачи нахождения максимальной взвешенной (с произвольными вещественными весами) упаковки T-путей для единичных пропускных способностей на вершинах неориентированного графа, где T - некое подмножество термиальных вершин. Для случая целых весов, который в случае единичных пропускных способностей просто соответствует максимальному набору вершинно-непересекающихся T-путей, эффективный алгоритм известен давно, поскольку задача может быть сведена к задаче нахождения максимального паросочетания. Случай произвольных вещественных весов получилось свести к нахождению целочисленной упаковки T-путей в сети с пропускными способностями на вершинах равными 2. Был сначала получен алгоритм, работающий за время O(mn), где m - количество ребер, n - количество вершин в графе, в котором использовалась техника дополняющих путей. Затем с помощью декомпозиции Эдмондса-Галлаи и некоторых дополнительных преобразований время работы было улучшено до O(m\sqrt{n}\log(n^2/m)/\log(n)). (Шень) Помимо классического понятия случайности бесконечной последовательности (по Мартин-Лёфу), существует и более слабое требование: средняя сложность последовательности (в битах информации на бит длины) максимальна (отношение сложности начала к его длине стремится к 1). Это свойство устойчиво относительно замены малой части битов: если биты изменены на множестве, предельная плотность которого равна нулю, то случайная последовательность может стать неслучайной, но сохранит это свойство максимальной средней сложности (технически оно называется "эффективная размерность 1") Возникает естественный вопрос: всякая ли последовательность эффективной размерности 1 может быть получена таким образом (из случайной по Мартин-Лёфу изменением небольшой доли битов). Оказывается, что да, и что ответ на этот (поставленный некоторое время назад) вопрос получается не чисто методами теории рекурсии, а соединением их с комбинаторными соображениями, а именно, теоремой Харпера. (Идея эта - в применении к конечным последовательностям - восходит к работе Верещагина с соавторами, которые показали, что можно увеличить сложность последовательности, заменив небольшое число битов.)
3 1 января 2018 г.-31 декабря 2018 г. Сложность определений и сложность вычислений, этап 3
Результаты этапа: Получены оценки биранговых чисел для частичного порядка, являющегося произведением двух булевых кубов. Для произведения двух кубов размерностей s и t соответственно обозначим через a(r,q) количество точек веса r в первом кубе и веса q во втором. Определим числа A_0(s,t,k) и A_1(s,t,k), которые равны сумме чисел a(r,q) при условиях r+q = k, r четно в первом случае и нечетно во втором. Доказаны неравенства A_1(s,n,m)<= A_1(n-2,n,m), A_0(s,n,m)<= A_0(n-1,n,m), A_1(s,n,m)<= A_0(n-1,n,m), где где 1<s<n, m - наибольшее нечетное число, не превосходящее 3n/4, а n больше 57. Эти неравенства применены к построению нетривиальной нижней оценки 13n/7 для мощности области определения универсальной функции для класса линейных булевых функций, где n - число переменных. Частичная булева функция f порождает линейную функцию g, если можно предъявить множество точек X из области определения функции f такое, что g(x) является единственной линейной функцией, совпадающей с f на множестве X. Если функция f (возможно частичная) порождает любую линейную функцию g, то f называется универсальной функцией для класса линейных функций. Доказано (М.Н. Вялый, А.А. Рубцов), что языки, распознаваемые детерминированными автоматами со словарём (Deterministic Set Automata) –– подклас класса P, а недетерминированные –– подкласс класса NP. Для каждой модели приведены примеры полных языков. Доказано, что проблема принадлежности слова языку для детерминированных автоматов со словарём лежит в классе P. Получено, что проблема пустоты для детерминированных и недетерминированных автоматов со словарём PSPACE-трудна, а в случае унарного алфавита словаря NP-трудна. Кроме того, охарактеризована алгоритмическая сложность задач проверки пустоты и вхождения в язык, заданный автоматом со словарем. Оказывается, что обе задачи для обоих видов автоматов со словарем являются PSPACE-полными. Получен важный структурный результат в области контекстно-свободных языков — комбиинаторная структурная лемма. В области классической алгоритмической статистики определены и изучены свойста антистохастических строк. Подробно изучены нормальные объекты (в том числе были решены ранее поставленные вопросы для них). Показана связь между теорией предсказания и алгоритмической статистикой. Была разработана алгоритмическая статистика с ограничением на ресурсы. Для полиномиального ограничения на память показана эквивалентность подходов в алгоритмической статистике, основанных на понятиях дефектов случайности и дефектов оптимальности. Для полиномиального ограничения на время доказано существование нестохастических объектов. Для такого варинта алгоритмической статистикой так же доказана её связь с теорией предсказания. Доказана #P-полнота задачи нахождения количества нулей многочлена, заданного в сжатом виде, над конечным полем. Новые верхние и нижние оценки на среднюю длину коммуникации для интерактивного аналога теоремы Вольфа --- Слепяна. А именно, верхняя оценка вида H + 2\sqrt{H} + O(\log(1/\varepsilon), где H --- условная энтропия входа Передающего при известном входе Принимающего, а \varepsilon --- вероятность ошибки. Пример случайных величин с нижней оценкой H + \Omega(1/\varepsilon) Новые оценки на коммуникационную сложность задачи Gap Hamming Distance. В этой задаче входы Алисы и Боба либо L-близки в смысле Хемминговского расстояния, либо U-далеки (здесь L, U --- параметры задачи). Требуется определить, какой из двух случаев выполнен. Доказано, что вероятностная коммуникационная сложность этой задачи с односторонней ошибкой равна L^2/U (с точностью до множителя log L). Построен параллельный протокол, достигающий верхней оценки. Приведен новый пример гаджета, достигающего лучших из известных на данный момент параметров лифтинга от детерминированной сложности деревьев разрешения к детерминированной коммуникационной сложности. Доказана невозможность построения гаджетов с лучшими параметрами с текущей техникой. Исследована сложность задача распознавания бесповторных булевых функций. Доказано, что эта задача coNP полна для 1-повторных монотонных булевых формул глубины 3. Доказано, что эта задача полиномиально разрешима для дизъюнкции бесповторной монотонной КНФ и бесповторной монотонной ДНФ. Для произвольного постоянного d получена новая нижняя оценка на k, для которого существует булева схема глубины d, вычисляющая функцию голосования от n переменных, и состоящая из функций голосования от не более чем k переменных. Мы получили новое неравентво для энтропии Шеннона (новый пример из класса так называемых существенно условных информационных неравенств) и предложили коминаторную интерпретацию этого неравенства. Мы использовали методы теории информации для оценки хроматического числа графа (с определенными комбианторными ограничениями на раскраску), а также в новом методе доказательства нижних оценок для бикликового покрытия двудольных графов. Мы изучили комбинаторный вариант схемы кодирования Вольфа и Слепяна. В данной задаче предполагается, что два отправителя имеют в своем распоряжении двоичные слова X и Y соответственно; длина каждого слова равна n, а расстояние Хэмминга между ними не более $c n$ для некоторой константы $c$. Отправители сжимают свои слова и пересылают результаты Получателю. Затем Получатель должен восстановить оба слова X и Y. Цель состоит в том, чтобы минимизировать длину передаваемых сообщений. Мы получили новую нижнюю оценку для схем с так называемым синдромным кодированием, в котором хотя бы один из Отправителей использует линейное кодирование входной строки. Для варианта данной задачи с рандомизированным кодированием был известен теоретический оптимум коммуникационной сложности. Однако не было ищвестно эффективных протоколов, достигающих оптимальной длиной сообщений. Мы решили данную задау и построили рандомизированный коммуникационный протокол с полиомиальным временем кодирования и декодиования, который обеспечивает оптимальную коммуникационную сложность. Получено точное соотношение между следующими двумя видами сложности вычислимых бесконечных 0-1-последовательностей. (1) Колмогоровская сложность бесконечной последовательности, релятизивизованная оракулом 0', определяется, как наименьшая длина программы, которая по любому натуральному числу n вычисляет начало последовательности длины n. Эта сложность обозначается через K'. (2) Неравномерная предельная сложность бесконечной последовательности определяется как наименьшее m, для которого для почти всех натуральных чисел n существует программа длины не более m, которая по n вычисляет начало последовательности длины n (эта программа может быть разной для разных n). Эта сложность обозначается через M_{\infty}. Ранее не было известно никаких соотношений между этими двумя видами сложности за исключением того, что сложность K&#39; может быть конечной для невычислимых последовательностей (например, для характеристической функции множества 0'), в то время как, сложность M_{\infty} может быть конечной только для вычислимых последовательностей. Но наиболее интересным является случай вычислимых последовательностей. Мы доказали, что для любой последовательности x сложность K'; не больше сложности M_{\infty} с точностью до постоянного слагаемого: K'(x)<M_{\infty}(x)+O(1). С другой стороны мы установили, что разрыв между K' и M_{\infty} может быть сколь угодно большим. Точнее, какую бы вычислимую функцию f мы ни выбрали, для всех m существует вычислимая последовательность x, для которой K'(x)<m + c, но M_{\infty}(x)>f(m). Константа c в первом неравенстве зависит от функции f. В доказательство неравенства K'x)<M_{\infty}(x)+O(1) мы применили метод, который раньше не встречался в литературе. А именно мы доказали <<лемму об обрезании листьев>>: Для любого перечислимого множества S двоичных слов ширины не более w (это означает, что для всех n множество содержит не более w слов длины n) существует разрешимое относительно 0'; двоичное дерево, которое не содержит листьев, имеет ширину не больше w и содержит все бесконечные пути в S (бесконечным путём в множестве слов S называется любая бесконечная 0-1-последовательность, у которой почти все начала принадлежат S). Разрешимость дерева означает существование алгоритма, которой по слову определяет, принадлежит ли оно дереву. Программа этого алгоритма может быть найдена по программе перечисления S и по w. Эта лемма может оказаться полезной и в других исследованиях по алгоритмической теории деревьев.В доказательстве второго утверждения (о разрыве между K' и M_{\infty}) мы применили игровой метод. Пусть дан некоторый натуральный параметр w. Рассмотрим игру двух игроков, называемых Алисой и Бобом. Игроки ходят по очереди и на каждом ходу любой из игроков может покрасить любое двоичное слово (мы будем представлять двоичные слова, как вершины двоичного дерева). Алиса красит слова в зеленый цвет, а Боб в красный (одно и то же слово может быть покрашено в оба цвета). При этом Алисе для любого n разрешается покрасить не более w слов длины n. Игра продолжается бесконечное количество ходов и после этого Алиса объявляется выигравшей в двух случаях: (1) в множестве зеленых вершин существует бесконечный путь, бесконечное количество вершин которого не покрашены в красный цвет, причем этот путь составлен из лексикографически максимальных зеленых вершин каждой длины или (2) для некоторого n есть w краснo-зеленых слов длины n. Оказывается, что для любого w в указанной игре существует вычислимая выигрышная стратегия для Алисы. Эта стратегия строится рекурсивно. Для w=1 выигрышная стратегия очевидна (Алиса красит в зеленый цвет любой бесконечный путь в двоичном дереве), а затем из выигрышной стратегии в w-игре строится выигрышная стратегия в w+1-игре. Чтобы доказать теорему, мы применяем вычислимую выигрышную стратегию Алисы в 2^{f(m)}-игре против следующей &quot;слепой&quot; стратегии Боба: Боб красит слово x длины n как только найдется программа p длины меньше f(m), которая на входе n выдает результат x. Для этого Боб развертывает вычисление всех программ длины меньше f(m) на всех входах и, как только к его очередному ходу какая-то программа остановилась на входе n, и напечатала слово x длины n, он красит слово x. Эта стратегия Боба вычислима и для каждого n Боб покрасит менее 2^{f(m)} слов длины n. Поэтому Алиса выигрывает по первой причине: существует бесконечный путь в двоичном дереве, все вершины которого покрашены в зеленый цвет, и бесконечное количество вершин не покрашены в красный цвет. Значит на этом пути бесконечно много начал имеют колмогоровскую сложность не менее f(m) при известной длине. Иными словами для выигрышного зеленого пути x выполнено M_{\infty}(x)> f(m). С другой стороны, поскольку стратегии Алисы и Боба вычислимы, множество вершин, покрашенных в зеленый цвет, будет перечислимым. Кроме того, оно имеет ширины не более f(m). Отсюда следует, что для зеленого пути x выполнено M_{\infty}(x)<f(m)+O(1), а значит M_{\infty}(x) конечно. Отсюда следует вычислимость x. Наконец, указанный зеленый путь может быть вычислен по m с помощью оракула 0': задавая ему вопросы можно для каждого n найти лексикографически минимальное зеленое слово длины n. Поэтому K'(x)< log m+O(1) (алгоритму, вычисляющему x, нужно знать само число m).

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

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

Прикрепленные файлы

№ Имя Описание Имя файла Размер Добавлен