В связи с техническими работами в центре обработки данных, возможность загрузки и скачивания файлов временно недоступна.
 

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

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

грант РФФИ

Этапы НИР

# Сроки Название
1 1 января 2012 г.-31 декабря 2012 г. Сложность определений и сложность вычислений
Результаты этапа: Опубликована монография по колмогоровской сложности, содержащая подробное изложение многих результатов последних двух десятилетий, которые не вошли в другие монографии о колмогоровской сложности. Получены новые дважды экспоненциальные нижние оценки весов полиномиальных пороговых элементов ограниченной степени для явных булевых функций. Доказана универсальность задач регулярной реализуемости в классе задач разрешения. Изучена сложность задачи нахождения лексикографически минимального и максимального суффикса подстрок заданной строки. Получена структура данных, позволяющая после предобработки строки длины $n$ за время $O(n \log^{O(1)} n)$ находить вышеуказанные экстремальные суффиксы в любой заданной подстроки за время $O(\log^{O(1)} n)$. Получен полностью комбинаторный переборный алгоритм для задачи разрезания графа на две равные части (minimum bisection), с помощью которого удалось найти оптимальные решения для задач размерности от тысячи до миллиона. Значительно упрощено доказательство теоремы Мучника об условной колмогоровской сложности с ограничением на память и время. Введено понятие колмогоровского экстрактора с ограничением на память и доказано существование этих объектов с такими же параметрами, что и без ограничений на память. Доказано существование вычислимой всюду определённой функции, которая по любому слову выдаёт список слов квадратичного размера, содержащий самое короткое с точностью до постоянного слагаемого описанием исходного слова. Доказан конструктивный вариант эргодической теоремы для случайных по Мартин-Лёфу последовательностей. Построены устойчивые к ошибкам наборы плиток, имеющие замощения лишь высокой сложности. Обнаружены новые свойства так называемых "условных" неравенства для энтропии Шеннона.
2 1 января 2013 г.-31 декабря 2013 г. Сложность определений и сложность вычислений
Результаты этапа: Полученные за отчетный период важнейшие результаты Коммуникационная сложность. Доказано, что любой вероятностный коммуникационный протокол который приблизительно вычислияет условную сложность x относительно y (или сложность пары x.y) для двоичных слов x, y длины n, должен передавать примерно n битов. Сложность в среднем. Показано, что если существует односторонняя функция, то класс полиномиально вычислимых ансамблей вероятностных распределений (PComp) не инвариантен относительно изменения кодирования. Алгоритмическая статистика. Доказано, существуют слова, для которых имеются достаточные статистики малой сложности, но все точные достаточные статистики имеют большую сложность. (Достаточной статистикой для слова x называется любое моножество A, содержащее x, для которого сумма колмогоровской сложности A и логарифма мощности A примерно равна колмогоровской сложности самого слова x. Такая статистика называется точной, если тотальная условная сложность A при известном x мала.) Доказано существование бесконечной бинарной последовательности, для которой сумма по префиксам отношения априорной дискретной и априорной непрерывной вероятности расходится. Рассмотрены обобщения задачи о различении слов подсловами. Первое из них состоит в том, что количество вхождений подслова в слово заменяется на количество вхождений подслова в слово на позициях, имеющих фиксированный остаток по некоторому модулю. Второе обобщение состоит в том, что вместо двоичных последовательностей рассматриваются возрастающие последовательности натуральных чисел. Различение в данном случае происходит в два этапа: на первом выбирается некоторое число и последовательности редуцируются по модулю этого числа, а на втором последовательности остатков сравниваются по кратностям вхождения в них подслов заданной длины. В обоих случаях получены степенные нижние оценки на сложность различения чисел. Доказано, что в случае подслов длины 1 оценка оптимальна с точностью до логарифмического множителя. Получены приложения этой задачи к задаче различения слов автоматами. Графовые алгоритмы. Получен способ дополнить ранее известный алгоритм быстрого приближённого вычисления минимального среднего веса рёбер на цикле в графе вычислением приближённо оптимального цикла. Это удалось сделать без ухудшения оценки времени работы алгоритма. Поиск кратчайших путей. В графе можно искать кратчайшие пути с помощью систем пересадок: для каждой вершины мы храним несколько пересадочных пунктов и расстояния до них, что позволяет быстро находить путь ровно с одной пересадкой. В последнее время были найдены алгоритмы поиска таких систем передадок, работающие быстро на практике, но не имеющие теоретического обоснования. Задачу можно свести к задаче о покрытии множества и получить приближенный алгоритм. Была проделана работа по реализации данного алгоритма и разработан вариант с улучшенной теоретической оценкой времени работы. Матричные игры. В области матричных игр рассматривались игры с двумя и тремя исходами, с двумя игроками, с нулевой суммой и с $n$ чистыми стратегиями для каждого из игроков. Для таких игр доказаны точные асимптотические нижние и верхние оценки $n^{-O(n)}$ и $n^{-\Omega(n)}$, соответственно, минимальной вероятности, которая может встретиться в оптимальной смешанной стратегии. Эти результаты опубликованы в журнале Discrete Applied Mathematics.
3 1 января 2014 г.-31 декабря 2014 г. Сложность определений и сложность вычислений
Результаты этапа: 1) Издана книга по колмогоровской сложности (Н.К. Верещагин, В.А. Успенский, А. Шень. Колмогоровская сложность и алгоритмическая случайность. Издательство МЦНМО. 2013), которая в ходе выполнения проекта переведена авторами на английский язык. Перевод предложен к публикации в издательство переводов Американского математического общества (AMS translations). 2) Установлено, что объект "количество слов сложности не выше данной" не инваринты относительно выбора оптимального декомпрессора: для двух разных декомпрессоров получающуеся слова могут иметь большую тотальную условноую сложность относительно друг друга. То же самое относится к самой долгоиграющей программе данной длины. 3) Введено понятие сильной достаточной статистики. Это понятие позволяет отделить хорошие и плохие статистики для данного слова. Установлено существование "странных" слов, для которых существуют достаточные статистики малой сложности, но все точные достаточные статистики имеют большую сложность. Причем, такие слова могут появляться с большой вероятностью при случайном выборе слов из некоторого множества. (Достаточной статистикой для слова x называется любое моножество A, содержащее x, для которого сумма колмогоровской сложности A и логарифма мощности A примерно равна колмогоровской сложности самого слова x. Такая статистика называется точной, если тотальная условная сложность A при известном x мала.) 4) Установлены почти точные оценки коммуникационная сложность задачи вычисления колмогоровской сложности пары слов (одно слово находится у Алисы, а другое у Боба) для вероятностных коммуникационных протоколов. Разработан новый способ преобразования коммуникационных протоколов с частными случайными битами в коммуникационные протоколы с общими случайными битами с небольшим увеличением информационной сложностью. Для коммуникационных протоколов с общими случайными битами и небольшой информационной сложностию разработан новый метод преобразования в протоколы с малой коммуникационной сложностью. 5) Доказано существование вычислимой всюду определённой функции, которая по любому слову $x$ выдаёт список из $O(|x|^2)$ слов, причем одно из них является самым коротким (с точностью до постоянного слагаемого) описанием для $x$. Доказано, что оценка $O(|x|^2)$ в такой формулировке неулучшаема. Кроме того, установлено, что если требуется лишь, чтобы список содержал самое короткое описание с точностью до логарифма длины $x$), то можно найти за полиномиальное время такой список полиномиального размера. C помощью техники, использованной в доказательстве этого результата, удалось получить улучшение эффективной версии теоремы Мучника с ограничением времени: для любых слов $b,a$ существует программа, переводящая $b$ в $a$ длины $K(a|b)+O(\log n)$, сложность которой с полиномиальным ограничением времени относительно $a$ есть $O(\log n)$ (раньше вместо $O(\log n)$ был некоторый полином от логарифма). 6) Сложность в среднем. Показано, что если существует односторонняя функция, то класс полиномиально вычислимых ансамблей вероятностных распределений (PComp) не инвариантен относительно изменения кодирования. 7) Получен результат, показывающий связь трех схожих определений "самого большого простого числа": а именно самого большого простого числа с точки зрения обычной Колмогоровской сложности, префиксной Колмогоровской сложности и числа, такого что сумма априорной дискретной вероятности начиная с него мала. Оказывается, что они отличаются не более чем на логарифм и эта оценка точна. 8) Построен вариант доказательства существования почти периодических последовательностей с регулятором, быстро растущим от прямого произведения с периодической последовательностью. Новый вариант отличается тем, что исходный регулятор, подвергающийся увеличению, превышает заданную быстрорастущую функцию для всех достаточно больших значений параметра, а не только для бесконечно многих. 9) В области сложности булевых схем исследовались веса полиномиальных пороговых элементов. А именно, исследовался вопрос о том, насколько большие веса могут потребоваться для вычисления заданной булевой функции пороговыми элементами фиксированной степени. Был найден пример функции от $n$ переменных, для которой эта величина достигает значения $2^{c 2^{2n/5}}$, где $c$ -- некоторая константа. 10) В области матричных игр рассматривались игры с двумя и тремя исходами, с двумя игроками, с нулевой суммой и с $n$ чистыми стратегиями для каждого из игроков. Для таких игр доказаны точные асимптотические нижние и верхние оценки $n^{-O(n)}$ и $n^{-\Omega(n)}$, соответственно, минимальной вероятности, которая может встретиться в оптимальной смешанной стратегии. Эти результаты опубликованы в журнале Discrete Applied Mathematics. 11) В области исследования запросов к онтологическим базам данных исследовалась длина первопорядковых переписываний таких запросов. Было доказано, что для древовидных запросов и теорий постоянной глубины больше 1 для некоторых конъюнктивных запросов не существует полиномиальных позитивно-экзестенциальных переписываний. Для получения этого результата потребовалось исследовать так называемые древовидные гиперграфовые программы и их вычислительную силу. 12) Проведен сравнительный анализ отношения рационального доминирования на множестве контекстно-свободных языков и классификации контекстно-свободных языков по алгоритмической сложности соответствующих им задач регулярной реализуемости (проверка непустоты пересечения регулярного языка и фиксированного языка — фильтра). Доказано, что полным относительно рационального доминирования КС фильтрам отвечают P-полные задачи регулярной реализуемости. Доказана грубость алгоритмической классификации по сравнению с отношением рационального доминирования: найдены примеры неполных относительно рационального доминирования языков, которым отвечают P-полные задачи регулярной реализуемости. 13) Для нескольких алгоритмов построения систем пересадок, которые ранее считались эвристическими, мы нашли верхние и нижние оценки на качество приближения к оптимальной системе пересадок. Тем самым у алгоритмов появилось теоретическое обоснование. Также мы доказали NP трудность задачи поиска оптимальной системы пересадок, что ранее было гипотезой.

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

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