Использование колмогоровской сложности для установления нижних оценок сложности доказательства?

11

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

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

В этой диссертации диссертацию " О сложности пропозициональных систем доказательств" Метод несжимаемости из Сложности Колмогорова используется для получения нижней оценки Уркхарта для класса тавтологий. Интересно, есть ли более сильные результаты с использованием метода несжимаемости или другие результаты из колмогоровской сложности?Ω(n/log⁡n)

lower-bounds proof-complexity kolmogorov-complexity Мухаммед Аль-Туркистани
источник
4
Колмогоровская сложность не кажется полезной для тавтологов. Для любой формальной системы лексикографически первое доказательство того, что битная формула является тавтологией, на самом деле чрезвычайно сжимаемо: ее можно описать в битах, указав формулу вместе с программой, которая пробует все доказательства в некоторая формальная система в лексикографическом порядке. Было бы более разумно взглянуть на ограниченные во времени версии колмогоровской сложности. nn+O(1)
Райан Уильямс
Мне было непонятно, я имею в виду колмогоровскую сложность результатов. Вопрос отредактирован.
Мухаммед Аль-Туркистани
3
Комментарий Райана все еще уместен, даже после редактирования. Если вы не ограничите какой-либо ресурс, колмогоровская сложность любого доказательства является константой (для фиксированного счетчика доказательств грубой силы) плюс размер предложения. Таким образом, вы не можете получить лучшие нижние границы, чем линейные.
Андрас Саламон
2
Ваш вопрос конкретно задает вопрос о «суперполиномиальных нижних границах». Аргумент Райана показывает, что ответ тривиально нет, поскольку колмогоровская сложность не более чем линейна. Нижняя граница Галези является сублинейной, не говоря уже о суперполиноме.
Андрас Саламон
1
@turkistany: см. meta.cstheory.stackexchange.com/questions/300/… .
Каве

Ответы:

1

Арвинд, Коблер, Мундхенк и Торан ввели понятие ограниченной во времени недетерминированной сложности экземпляра. Основываясь на быстром чтении, кажется, что они используют меру сложности Колмогорова, которая зависит от размера самой короткой недетерминированной ТМ. Они смогли доказать существование трудно доказываемых тавтологий под понятием твердости, основанным на недетерминированной сложности экземпляра.

Викраман Арвинд, Йоханнес Коблер, Мартин Мундхенк, Якобо Торан, недетерминированная сложность экземпляров и трудно доказываемые тавтологии,

Мухаммед Аль-Туркистани
источник