Рассмотрим следующие рассуждения:
Пусть обозначим сложность Колмогорова из строки . Теорема Чайтена о неполноте гласит, чтох
для любой последовательной и достаточно сильной формальной системы , существует постоянную (зависящую только от формальной системы и ее языка), что для любых строк , не может доказать , что .T x S K ( x ) ≥ T
Пусть - булева функция от переменных, а колмогоровская сложность ее спектра не больше . Пусть будет сложностью схемы , то есть размером минимальной схемы, вычисляющей . н к с ( ф н ) ф н ф н
(Грубая) верхняя граница для равна S ( f n ) ≤ c ⋅ B B ( k ) ⋅ n для константы c, а B B ( k ) - функция занятого бобра (максимально возможные шаги a остановка машины Тьюринга с описанием размера k может выполнить). (Для каждого 1 в спектре постройте минтерм соответствующего присвоения истины и возьмите ИЛИ из всех этих минтермов вместе.)
Предположим теперь, что для бесконечного семейства булевых функций мы имеем формальное доказательство того, что L требует схем с суперлинейным размером, т.е.
где g ( n ) ∈ ω ( 1 ) .
Если мы возьмем достаточно большим, мы будем иметь g ( n ) > c ⋅ B B ( T )
В частности, это было бы доказательством того, что колмогоровская сложность спектра функции не меньше T , что невозможно.
Это приводит к двум вопросам:
1) Должно быть что-то не так в рассуждениях выше. Главным образом потому, что это сделало бы нижние границы суперлинейной схемы формально не доказуемыми.
2) Знаете ли вы о похожих подходах для демонстрации барьеров для нижних границ, то есть, показывающих, что определенные типы (контуров) нижних границ формально недоказуемы?
Ответы:
источник
источник