ИСТИНА

Проект направлен на решение нескольких проблем, объединенных тем, что все они относятся к сложности: вычислительной сложности (в частности, построению быстрых алгоритмов) и сложности определений (колмогоровской сложности).

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 трудность задачи поиска оптимальной системы пересадок, что ранее было гипотезой.