Аргументы за / против гипотезы Колмогорова о сложности схемы P

Согласно (непроверенному) историческому описанию, Колмогоров считал, что каждый язык в имеет линейную сложность схем. (См. Предыдущий вопрос о гипотезе Колмогорова о том, что имеет цепи линейного размера .) Обратите внимание, что из этого следует, что . $\mathsf{P}$ $P$ $\mathsf{P}\neq \mathsf{NP}$

Гипотеза Колмогорова, однако, видимо, вероятно, потерпит неудачу. Например, Райан Уильямс пишет в недавней статье: «Эта гипотеза была бы удивительной, если бы она была верной. Для языков в требующих времени, маловероятно, что сложность таких проблем будет магически уменьшаться до размера , просто потому, что для каждой длины входа может быть разработана другая схема ". $\mathsf{P}$ $n^{100^{100}}$ $O(n)$

С другой стороны, Андрей Колмогоров (1903-1987) широко известен как один из ведущих математиков 20-го века. Довольно сложно представить, что он предложил бы совершенно абсурдную гипотезу. Поэтому, чтобы понять это лучше, я попытался найти некоторые аргументы, которые могли бы фактически поддержать его удивительное предположение. Вот что я мог придумать:

Предположим, что . Тогда мы можем выбрать язык , такой, что имеет суперлинейную сложность как в равномерной, так и в неоднородной модели. Тогда есть две возможности: $\mathsf{P}\not\subseteq \mathsf{SIZE}(lin)$ $L\in \mathsf{P}$ $L$

Существует известный явный алгоритм (машина Тьюринга) , который принимает $L$ . Из этого мы можем построить семейство явных функций, которое должно иметь сложность суперлинейной схемы. Тем не менее, это может показаться маловероятным, поскольку никто не смог найти такой пример за более чем 60 лет интенсивных исследований цепей.
Не Там будет не известно явного алгоритма $L$ . Например, его существование доказывается неконструктивными средствами, такими как Аксиома выбора. Или, даже если явный алгоритм существует, никто не смог его найти. Однако, учитывая, что существует бесконечно много языков, которые могут играть роль $L$ , маловероятно, что они все будут вести себя таким недружественным образом.

Но тогда, если мы отклоним оба варианта как маловероятные, единственная оставшаяся возможность - то, что такой $L$ не существует. Это означает, что $\mathsf{P}\subseteq \mathsf{SIZE}(lin)$ , что в точности является гипотезой Колмогорова.

Вопрос: Можете ли вы представить какой-либо дополнительный аргумент за / против гипотезы Колмогорова?

cc.complexity-theory circuit-complexity ho.history-overview Андрас Фараго
источник

Интересно: есть ли у нас кандидаты на опровержение гипотезы Колмогорова? Конечно, можно рассмотреть любую проблему, которая доказуемо имеет суперлинейную сложность. Может быть, некоторые из них, скорее всего, не имеют цепей линейного размера?

Бруно

давайте посмотрим правде в глаза, никто не имеет ни малейшего понятия. (повторяю цитату Голдмана о Голливуде: «никто ничего не знает».) (неопубликованная) гипотеза, возможно, была открыта даже дольше, чем P =? NP. Тем не менее, грубая идея / угол, который стоит изучить: теория сжатия и сжимаемость. это то, на что намекает Уильямс, и, возможно, оно может быть в основе многих разделений классов сложности. идея заключается в том, что существуют базовые способы / алгоритмы для кодирования данных, и некоторые шаблоны по своей природе сложнее сжать с использованием (любого произвольного) кодирования. но в этой области, похоже, тоже очень мало результатов.

августа

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

vzn

@Bruno: я бы предположил, что -полные проблемы были бы хорошими кандидатами, например, линейное программирование или проблема значений схемы. Если то эти проблемы не могут быть решены даже неравномерно по размеру poly и log-логарифмической глубине, поэтому, по крайней мере, кажется разумным предположить, что таких проблем быть не должно разрешимый в линейном размере (и неограниченной глубине) либо. Определитель может быть другим разумным кандидатом. Но это всего лишь предложения - у меня нет веских оснований полагать, что у них суперлинейный размер схемы.

P

$\mathsf{P}$

P ⊈ N C

$\mathsf{P} \not\subseteq \mathsf{NC}$

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

Ответы:

Сноска моей статьи, которую вы цитируете, относится также к эвристическому «аргументу», по крайней мере, к тому, что мы считаем интуицией Колмогорова - положительным решением тринадцатой проблемы Гильберта.

http://en.wikipedia.org/wiki/Hilbert's_thirteenth_problem

В частности, Колмогоров и Арнольд доказали, что любая непрерывная функция от переменных может быть выражена как композиция из «простых» функций: сложение двух переменных и непрерывных функций от одной переменной. Следовательно, по «базису» непрерывных функций с одной переменной и сложению с двумя переменными каждая непрерывная функция от переменных имеет «сложность схемы» . $n$ $O(n^2)$ $n$ $O(n^2)$

Кажется, Колмогоров полагал, что существует дискретный аналог, где «непрерывный по переменным» становится «булевым по переменным и вычисляемым в поли -время», а приведенный выше «базис» становится булевыми функциями с двумя переменными. $n$ $n$ $(n)$

Райан Уильямс
источник

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

P \neq N P

$P\neq NP$

Андрас Фараго

Блокпосты? Я не думаю, что кто-то нашел дорогу :) Поскольку большинство людей считает, что не имеет цепей размера , для каждого фиксированного , вероятно, мало кто даже искал дорогу.

P

$P$

O (n^{k})

$O(n^k)$

k

$k$

Райан Уильямс

Ответ Stasys на предыдущий вопрос дает некоторую интуицию, потенциально в пользу: /cstheory//a/22048/8243 . Я постараюсь изложить здесь, как я понимаю. Ключевая интуиция состоит в том, чтобы рассматривать схему как не алгоритм, а кодировку набора (набора, который он принимает). Мы можем получить верхнюю границу размера кодирования по времени выполнения алгоритма (то есть преобразовать время TM в схему размера ), но не ясно, какие обратные отношения должны существовать. Если язык находится в , то, возможно, это подразумевает, что членство достаточно «локально», чтобы кодироваться очень кратко. $t$ $t$ $\mathsf{P}$

То есть членство в является утверждением о времени выполнения алгоритма, тогда как линейные схемы (возможно) являются утверждением о размере кодирования наборов слов фиксированной длины. Оба являются утверждениями о простоте языка, но они живут в разных мирах. $\mathsf{P}$

Другая интуиция, о которой упоминает Стасис, происходит от «индикаторной строки» языка, которую давайте формализуем как бесконечную строку, где бит равен если я лексикографическая строка присутствует в языке, а в противном случае - . (Polytime) TM для языка является (быстрым) оракулом для строки - учитывая в двоичном коде, создает бит й. Схема (линейного размера) для входов длины является (кратким) оракулом для префикса длины строки. Гипотеза становится «любой бесконечной строкой, в которой есть« быстрый »оракул, есть« краткие »префиксы-оракулы». $j$ $1$ $j$ $0$ $j$ $j$ $n$ $2^n$

Ничто из вышеперечисленного не объясняет, почему и" linear "могут быть правильными соответствующими параметрами для оператора, но я думаю, что они показывают, что одна естественная интуиция - эти схемы действуют как алгоритмы, а более сложные алгоритмы требуют аналогично сложные схемы - могут вводить в заблуждение. $``\mathsf{P}"$

усул
источник