Колмогоровские приложения сложности в вычислительной сложности

44

Неформально говоря, колмогоровская сложность строки - это длина самой короткой программы, которая выводит . Мы можем определить понятие «случайная строка», используя ее ( является случайным, если ). Легко видеть, что большинство строк случайные (коротких программ не так много). $x$ $x$ $x$ $K(x) \geq 0.99 |x|$

Теория сложности Колмогорова и алгоритмическая теория информации в настоящее время достаточно развиты. И есть несколько забавных примеров использования колмогоровской сложности в доказательствах различных теорем, которые не содержат ничего о колмогоровской сложности в своих высказываниях ( конструктивная LLL , неравенство Лумиса-Уитни и т. Д.).

Есть ли хорошие применения колмогоровской сложности и алгоритмической теории информации в вычислительной сложности и смежных областях ? Я чувствую, что должны быть результаты, использующие колмогоровскую сложность в качестве простой замены простых подсчитывающих аргументов. Это, конечно, не так интересно.

cc.complexity-theory big-list co.combinatorics it.information-theory ilyaraz
источник

2

Вы ищете только примеры проблем, которые на первый взгляд не имеют ничего общего с колмогоровской сложностью? Есть много результатов о вычислительной сложности различных множеств, определенных в терминах колмогоровской сложности (наиболее заметно множество случайных по Колмогорову строк), а также множество результатов, связывающих ограниченную в ресурсах сложность Колмогорова со стандартными вещами сложности (такими как P vs NP). , факторинг и т. д.). Но я не уверен, что вы ищете последнее или нет.

Джошуа Грохов

1

> Вы ищете только примеры проблем, которые на первый взгляд не имеют ничего общего с колмогоровской сложностью? Точно так.

Ильяраз

16

Лэнс Фортнау написал статью на эту тему: сложность Колмогорова и сложность вычислений

Вы также должны проверить «Введение в колмогоровскую сложность и ее приложения » Ли и Витаньи, окончательную книгу на эту тему. В частности, в главе 6 «Метод несжимаемости» обсуждается ряд приложений по сложности, таких как доказательство сложности Колмогорова леммы о переключении Хастада (из « Цепи нижних границ а-ля Колмогорова » Фортнау и Лапланте).

И есть приложения в сложности коммуникации (например, сложность Колмогорова и комбинаторные методы в сложности коммуникации Каплана и Лапланте).

Ян
источник

1

Спасибо. Эта статья очень приятная и полезная, но мне нужны приложения без упоминания о K-сложности в выражениях.

Ильяраз

1

Ильяраз, хотя большинство результатов, упомянутых в этой статье, являются следствиями, а не приложениями, вы можете рассматривать характеристики классов сложности по колмогоровской сложности как слабую форму «приложения».

Джошуа Грохов

Я обновил пост с некоторыми ссылками, которые могут больше соответствовать тому, что вы ищете.

Ян

14

Всего несколько дней назад Скотт Ааронсон использовал аргумент, основанный на колмогоровской сложности, чтобы показать эквивалентность выборки и поиска . Далее он утверждает, что в своем рассуждении колмогоровская сложность используется существенным образом, а не просто как счетный аргумент.

Мартин Шварц
источник

11

Этот результат Alon et al. можно получить с помощью колмогоровской сложности.

«Множество ребер E каждого конечного двудольного графа можно разбить на подмножества так, чтобы все получающиеся двудольные графы были почти регулярными». $\mathrm{poly}(\log |E|)$

ilyaraz
источник

кажется нелогичным. кто-нибудь знает о других результатах, касающихся двудольных графов и регулярных графов?

vzn

11

Одна отличная статья, о которой я знаю (в дополнение к другим замечательным статьям, упомянутым в других ответах):

Юрис Хартманис, Обобщенная колмогоровская сложность и структура возможных вычислений , FOCS 1983.

Главное, что я помню из этой статьи, - колмогоровская сложная конструкция оракула, отделяющего P от NP.

Еще одна статья, которая приходит на ум,

Аллендер и др., Power from Random Strings , FOCS 2002 ( версия ECCC ) и SICOMP 2006 .

Насколько я помню, последняя статья отделяет полноту-время полноты Тьюринга от полноты много-единичного лог-пространства в PSPACE, используя аргументы сложности Колмогорова. Конечно, это делает много других вещей, но я напоминаю, что разделение - это одно приложение, которое представляет самостоятельный интерес вне алгоритмической теории информации.

Dave Doty
источник

9

Также есть метод квантовой нижней границы, который использует колмогоровскую сложность:

« Нижние оценки для рандомизированной и квантовой сложности запроса с использованием аргументов Колмогорова » Софи Лапланте и Фредерика Магниеса

Робин Котари
источник

9

$s$ $K(s)$

(Теперь серьезно.) Даниил Мусатов недавно показал, что наивная дерандомизация может обеспечить разумные конструкции для объектов, которые, как обычно показывают, существуют неконструктивно с помощью вероятностного метода. Я думаю, что это, вероятно, обеспечит существенные будущие приложения ограниченной по Колмогорову сложности к вычислительной сложности.

Даниил Мусатов, Совершенствование ограниченной в пространстве версии теоремы об условной сложности Мучника с помощью "наивной" дерандомизации , CSR 2011, LNCS 6651, 64–76. doi: 10.1007 / 978-3-642-20712-9_6 ( препринт )

Смотрите также статьи, цитирующие это .

(Изменить: ссылка на более позднюю, опубликованную версию.)

Андраш Саламон
источник

1

Я бы сказал, что последняя статья применяет вычислительную сложность (а именно, псевдослучайный генератор Нисана) к ограниченной по Колмогорову сложности, а не наоборот.

Ильяраз

1

@ilyaraz: это точное резюме. Я утверждаю, что, учитывая ссылки в одном направлении, эти приложения должны работать и в другом направлении.

Андрас Саламон

8

Х. Бурман, Л. Фортнов и С. Лапланте. Ресурс-ограниченная колмогоровская сложность вновь. SIAM Journal of Computing, 31 (3): 887-905, 2002. ( журнал , веб-страница Лэнса ).

Включает приложения колмогоровской сложности, такие как:

Доказательство Валиант-Вазирани
Удовлетворительные назначения булевых формул могут быть перечислены во временном полиноме в выходном размере, если уникальное назначение может быть быстро найдено
Новое доказательство того, что БПП в Sigma_2 P
Несколько оракулов

Некоторые из вышеперечисленных были впервые доказаны в этой статье, тогда как другие являются просто новыми доказательствами старых теорем с использованием колмогоровской сложности.

Приложения ограниченной по Колмогорову сложности в теории сложности - хороший обзор Эрика Аллендера из других приложений. Хотя многие из результатов здесь являются следствиями, некоторые из них являются истинными приложениями, такими как следующее:

Кор 13: По сравнению с обычным оракулом, не существует псевдослучайного генератора, который был бы защищен от P / poly противников.
Thm 16 [Allender and Gore, 1991]: существует оракул, относительно которого все предикаты NE разрешимы в экспоненциальном времени и E = Union_k \ Sigma_k-TIME (n).

Оба доказательства используют колмогоровскую сложность значительно.

Джошуа Грохов
источник

Я предполагаю, что оригинальное доказательство Сипсера "BPP в Sigma_2" использовало колмогоровскую сложность.

Ильяраз

6

$D$ $D$

ilyaraz
источник

Кстати, в этой версии опроса есть недостаток доказательства. Впрочем, это можно исправить :)

Григорий Ярославцев

Хотите разработать?

Ильяраз

1 / n^{3}

$1/n^3$

1 / n^{1 + ϵ}

$1/n^{1 + \epsilon}$

5

Минимальная длина описания использует сложность Колмогорова (или ее аппроксимации и обобщения из-за неразрешимости) в теоретико-информационном обучении и теории вывода. В частности, MDL используется для поиска объяснений данных, которые естественным образом избегают переобучения.

Йорма Риссанен дает хорошее представление о своей концепции: http://www.mdl-research.org/jorma.rissanen/pub/Intro.pdf

Росс Снайдер
источник

3

Ты имеешь в виду что-то подобное, ильяраз?

http://arxiv.org/abs/1004.3993

Аарон Стерлинг
источник

Да, это кажется обнадеживающим.

ильяраз

Колмогоровские приложения сложности в вычислительной сложности

Ответы: