Гипотеза Колмогорова о том, что

28

В своей книге «Сложность булевых функций» Стасис Юкна упоминает (стр. 564), что Колмогоров считал, что каждый язык в P имеет цепи линейного размера. Никакой ссылки не упоминается, и я не могу ничего найти в Интернете. Кто-нибудь знает больше об этом?

Хамид
источник
4
Пейджинг @Stasys :)
Суреш Венкат
7
обратитесь также сюда rjlipton.wordpress.com/2009/02/12/is-np-too-big-or-p-too-small
T ....
19
Эта «догадка» Колмогорова - всего лишь слух. Конечно, это нигде не было опубликовано. В бывшем СССР «публикация» математики означала нечто иное: выступать на семинаре, рассказывать коллегам на обеде или еще что-то. Подсчет бумаг не был проблемой. Итак, я не могу исключить, что эту «гипотезу» только что рассказал Левину Колмогоров во время их похода на семинар в МГУ (Московский университет). (На самом деле, я также предписывал этот способ делать математику.) Так что не принимайте это всерьез - просто как «слух», который (что и говорить) не опровергался годами ...
Стасис
5
@vzn для любого фиксированного поскольку . Последнее усиливается до \ Sigma_2 ^ {\ mathsf {P}} по теореме Каннана . Psize(nk)PNPkkN:Σ4Psize(nk)Σ2P
Сашо Николов
2
@Stasys, вы должны опубликовать это как ответ, чтобы вопрос стал ответом (чтобы сайт не переместил его на первую страницу).
Каве

Ответы:

24

[Следуя предложению Каве, я помещаю свой (несколько расширенный) комментарий в качестве ответа]

Эта «догадка» Колмогорова - всего лишь слух. Это нигде не было опубликовано. В бывшем СССР «публикация» математики означала нечто иное, чем то, что она делает сегодня: выступить на семинаре или рассказать коллегам за ланчем. Подсчет бумаг не был проблемой. (На самом деле, я также предписывал этот способ математики.) Я не могу исключить возможность того, что эта «догадка» была только что высказана Левину Колмогоровым во время их похода на семинар в Московском университете. Так что не воспринимайте это слишком серьезно как формальное предположение; это просто слух, который (само собой разумеется) не опровергался в течение многих лет. Но поскольку такой гигант, как Колмогоров, всерьез задумался над этой проблемой и не исключил возможности «дьявольской власти», к гипотезе следует относиться достаточно серьезно,

Вот (очень, очень грубое) предположение о моем понимании этой гипотезы. Наша (очевидно ошибочная) интуиция о том, как работают схемы, основана на том, чтобы рассматривать вычисления программой как последовательный процесс, который постепенно собирает информацию о входной строке. Эта интуиция заимствована из нашего представления о том, как работает машина Тьюринга. Но каждая входная строка определяет подсхему (свидетельство или ). И чтобы схема была правильной, достаточно, чтобы множества подсхем для и не пересекались. То есть схема представляет собой компактное «локальное кодирование» данного разделаxf(x)=1f(x)=0f1(1)f1(0)n-CUBE. Длина этого кода представляет собой колмогоровскую сложность заданной двоичной строки длины . Однако алгоритм полиномиального времени делает больше: он дает одно «глобальное кодирование» всей бесконечной строки для всех . Теперь бесконечная строка допускающая кодирование размером должна быть «простой», а ее префиксы «должны» допускать еще более компактные «локальные» кодировки. Конечно, остается загадкой, почему Колмогоров считал, что «локальных» кодировок даже размера для некоторого тогда может быть достаточно ...fn2nfnfnccnc

PS Извините, забыл добавить: отличным подтверждением моего «тезиса» о том, что схемы следует рассматривать как (статические) коды, а не (динамические) алгоритмы, является знаменитая теорема Дэвида Баррингтона о том, что весь класс можно моделировать полиномом. размерные программы разветвления шириной 5. Представление «сбор информации» здесь совершенно неверно: даже неясно, как вычислить функцию большинства, сохраняя только 5 бит информации. Умная идея Дэвида была просто закодироватьNC1поведение заданной формулы с помощью конкретных последовательностей 5-перестановок и показать, что принятые и отклоненные строки получат разные коды. Дело в том, что ветвящаяся программа также не «вычисляет» - она ​​скорее кодирует входные строки своими подпрограммами: когда поступает входной сигнал, исчезают несогласованные ребра, и у нас есть код этого входного сигнала.

Стасис
источник
Существуют ли нетривиальные примеры языков, поддерживающих эту гипотезу?
Игорь Шинкарь
@ Игорь: я не знаю. Некоторые (слабые) признаки упомянуты здесь . На самом деле, я склоняюсь к ответу GMB: скорее всего, гипотеза была стимулирована их решением проблемы 13-го Гильберта, а не комбинаторными соображениями.
Стасис
8

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

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

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

Мне говорят, что, основываясь на некоторых деталях реализации доказательства этой теоремы, это можно рассматривать как непрерывный аналог утверждения, что .kPSIZE(nk)

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

GMB
источник
Можете
@GMB: хорошо наблюдаемый - это могло бы быть даже более близким объяснением причины, чтобы поднять эту гипотезу.
Стасис