Схема нижних границ и колмогоров сложности

21

Рассмотрим следующие рассуждения:

Пусть обозначим сложность Колмогорова из строки . Теорема Чайтена о неполноте гласит, чтохK(x)x

для любой последовательной и достаточно сильной формальной системы , существует постоянную (зависящую только от формальной системы и ее языка), что для любых строк , не может доказать , что .T x S K ( x ) TSTxSK(x)T

Пусть - булева функция от переменных, а колмогоровская сложность ее спектра не больше . Пусть будет сложностью схемы , то есть размером минимальной схемы, вычисляющей . н к с ( ф н ) ф н ф нfnnkS(fn)fnfn

(Грубая) верхняя граница для равна S ( f n ) c B B ( k ) n для константы c, а B B ( k ) - функция занятого бобра (максимально возможные шаги a остановка машины Тьюринга с описанием размера k может выполнить). (Для каждого 1 в спектре постройте минтерм соответствующего присвоения истины и возьмите ИЛИ из всех этих минтермов вместе.)S(fn)

S(fn)cBB(k)n
cBB(k)k1

Предположим теперь, что для бесконечного семейства булевых функций мы имеем формальное доказательство того, что L требует схем с суперлинейным размером, т.е.L={fn}nL

где g ( n ) ω ( 1 ) .

Snn0, g(n)nS(fn)
g(n)ω(1)

Если мы возьмем достаточно большим, мы будем иметь g ( n ) > c B B ( T )n

g(n)>cBB(T)

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

Это приводит к двум вопросам:

1) Должно быть что-то не так в рассуждениях выше. Главным образом потому, что это сделало бы нижние границы суперлинейной схемы формально не доказуемыми.

2) Знаете ли вы о похожих подходах для демонстрации барьеров для нижних границ, то есть, показывающих, что определенные типы (контуров) нижних границ формально недоказуемы?

Магнус Найти
источник
интересные идеи. Отчасти связан с доказательством Разборова / Рудича о «естественных доказательствах», которое очерчивает барьеры для P =? NP (но также, вероятно, применимо к другим классам разделения сложности, перечисленным в качестве примеров в статье). Вы читали эту статью? см. также барьеры P =? NP и барьеры / сложность монотонной цепи . кажущиеся намеки на то, что разделение классов сложности по структуре похоже на доказательства недоказуемости.
vzn
2
Можете ли вы рассказать о «спектре» f_n? Есть ли способ сформулировать вопрос, не ссылаясь на «спектр»?
ВЗН
вероятно, верно, что можно изучать сложность функций, изучая наименьшую ТМ [в смысле таблицы состояний / состояний], которая их вычисляет, и что это будет приблизительно соответствовать нижним границам схемы. если вы можете показать, что найти самую маленькую ТМ невозможно, а не трудно, у вас там что-то есть. однако «просто» найти наименьшую ТМ через каноническое перечисление цепей или ТМ. если вы задумаетесь над тем, почему этот подход работает, это может помочь понять, почему вопрос не приводит к проблеме.
ВЗН
1
(f(0,0,..,0),f(0,0,..,1),..,f(1,1,..,1))

Ответы:

11

NfnTNN>g1(cBB(T))BB

domotorp
источник
S
1

A(k)K(A(k))kkK(A(k))k

BB(T)

α(k)kα(k)K(0α(k)+1)>k

Юваль Фильмус
источник
Почему эта ситуация проблематична? Вы не дали программу, чей вывод был бы A (k), а ее длина была бы меньше k.
Домоторп
BB(k)k
Это проблематично в (возможно) том же смысле, что и первоначальный вопрос.
Юваль Фильмус
Я до сих пор не понимаю. Вы не выставляете строку и доказательство того, что ее колмогоровская сложность велика. Вы демонстрируете, что существует строка, сложность которой велика.
Сашо Николов
Я думаю, что они проблемные по-разному. Когда я это читаю, вы указываете на конкретное истинное утверждение, у которого нет доказательств. Излагая это в своем вопросе, я отмечаю, что это влечет за собой доказательство того, что не доказуемо.
Магнус Найди