В своей книге «Сложность булевых функций» Стасис Юкна упоминает (стр. 564), что Колмогоров считал, что каждый язык в P имеет цепи линейного размера. Никакой ссылки не упоминается, и я не могу ничего найти в Интернете. Кто-нибудь знает больше об этом?
28
Ответы:
[Следуя предложению Каве, я помещаю свой (несколько расширенный) комментарий в качестве ответа]
Эта «догадка» Колмогорова - всего лишь слух. Это нигде не было опубликовано. В бывшем СССР «публикация» математики означала нечто иное, чем то, что она делает сегодня: выступить на семинаре или рассказать коллегам за ланчем. Подсчет бумаг не был проблемой. (На самом деле, я также предписывал этот способ математики.) Я не могу исключить возможность того, что эта «догадка» была только что высказана Левину Колмогоровым во время их похода на семинар в Московском университете. Так что не воспринимайте это слишком серьезно как формальное предположение; это просто слух, который (само собой разумеется) не опровергался в течение многих лет. Но поскольку такой гигант, как Колмогоров, всерьез задумался над этой проблемой и не исключил возможности «дьявольской власти», к гипотезе следует относиться достаточно серьезно,
Вот (очень, очень грубое) предположение о моем понимании этой гипотезы. Наша (очевидно ошибочная) интуиция о том, как работают схемы, основана на том, чтобы рассматривать вычисления программой как последовательный процесс, который постепенно собирает информацию о входной строке. Эта интуиция заимствована из нашего представления о том, как работает машина Тьюринга. Но каждая входная строка определяет подсхему (свидетельство или ). И чтобы схема была правильной, достаточно, чтобы множества подсхем для и не пересекались. То есть схема представляет собой компактное «локальное кодирование» данного разделаx f(x)=1 f(x)=0 f−1(1) f−1(0) n -CUBE. Длина этого кода представляет собой колмогоровскую сложность заданной двоичной строки длины . Однако алгоритм полиномиального времени делает больше: он дает одно «глобальное кодирование» всей бесконечной строки для всех . Теперь бесконечная строка допускающая кодирование размером должна быть «простой», а ее префиксы «должны» допускать еще более компактные «локальные» кодировки. Конечно, остается загадкой, почему Колмогоров считал, что «локальных» кодировок даже размера для некоторого тогда может быть достаточно ...fn 2n f n f nc cn c
PS Извините, забыл добавить: отличным подтверждением моего «тезиса» о том, что схемы следует рассматривать как (статические) коды, а не (динамические) алгоритмы, является знаменитая теорема Дэвида Баррингтона о том, что весь класс можно моделировать полиномом. размерные программы разветвления шириной 5. Представление «сбор информации» здесь совершенно неверно: даже неясно, как вычислить функцию большинства, сохраняя только 5 бит информации. Умная идея Дэвида была просто закодироватьNC1 поведение заданной формулы с помощью конкретных последовательностей 5-перестановок и показать, что принятые и отклоненные строки получат разные коды. Дело в том, что ветвящаяся программа также не «вычисляет» - она скорее кодирует входные строки своими подпрограммами: когда поступает входной сигнал, исчезают несогласованные ребра, и у нас есть код этого входного сигнала.
источник
Я не настолько разбираюсь в этой теме, как Стасис, но я услышал другое обоснование этой гипотезы, которое я мог бы также поделиться.
Я слышал, что эта гипотеза была основана на положительном решении тринадцатой проблемы Гильберта, которая была совместно решена Комолгоровым и его учеником Арнольдом. Теорема (которая гораздо более общая, чем заявленная проблема Гильберта) гласит:
Мне говорят, что, основываясь на некоторых деталях реализации доказательства этой теоремы, это можно рассматривать как непрерывный аналог утверждения, что .∃kP⊂SIZE(nk)
Извините, я не квалифицирован, чтобы быть более точным, чем это - если кто-то еще слышал эту идею, возможно, они могли бы помочь мне.
источник