Сфера естественного доказательства барьера

Естественный барьер доказательств Разборова и Рудича утверждает, что при достоверных криптографических предположениях нельзя надеяться отделить NP от P / poly, найдя комбинаторные свойства функций, которые являются конструктивными, большими и полезными. Есть несколько хорошо известных результатов, которые удается обойти барьер. Есть также несколько работ, в которых обсуждаются возможные лазейки к трем условиям, например, результат Чоу, показывающий, что барьер чувствителен к слабым нарушениям крупности, и недавняя статья Чепмена и Уильямса.предложить, как можно избежать барьера, ослабив условие полезности. Мой вопрос заключается в том, есть ли какие-либо примеры или даже возможность избежать естественного барьера доказательств, не нарушая конструктивность, масштабность или полезность, а полностью выходя за его рамки. То есть мне совершенно не очевидно, почему каждый потенциальный метод доказательства должен основываться на нахождении комбинаторных «свойств», а затем разбивать все функции на те, которые имеют и не удовлетворяют этому свойству. Почему эта схема работы должна применяться ко всем возможным доказательствам, а если нет, то как будут выглядеть другие типы доказательств?

Пусть - функция, а C - класс алгоритмов, работающих на конечных срезах функции f . Каждый контур нижней границы вообще является доказательством того, что е ∉ С , для некоторых х и некоторых С . Рассмотрим «комбинаторное свойство булевых функций» P f , такое что$f: \{0,1\}^* \rightarrow \{0,1\}$$C$$f$$f \notin C$$f$$C$${\cal P}_f$

и P f (g)=0для всехg≠f.${\cal P}_f(f) = 1$${\cal P}_f(g) = 0$$g \neq f$

Доказательство того, что является доказательством того, что Р е является полезным против C , в терминологии Разборов и Рудич. То есть «полезность» абсолютно неизбежна - нет способа «выйти за пределы ее возможностей». Если вы вообще доказали нижнюю границу схемы, вы дали некоторые полезные свойства.$f \notin C$${\cal P}_f$$C$

Отметим, что если , то P f также конструктивен в терминологии Разборова и Рудича. Таким образом, для функций f, вычисляемых в E, но не в (скажем) P / p o l y , конструктивность также будет применяться по крайней мере к одному свойству булевых функций, которое полезно для P / p o l y .$f \in TIME[2^{O(n)}]$${\cal P}_f$$f$$E$$P/poly$$P/poly$

Итак, Разборов и Рудич более фундаментальны, чем вы могли подумать.

Вы правы: теорема о естественных доказательствах о естественных свойствах (и только неофициально о доказательствах). Сам Разборов написал две статьи одновременно, изучая класс формальных доказательств и нижние оценки сложности:

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

Первый изучает формализацию существующих доказательств нижней оценки в слабых фрагментах арифметики (верхние оценки сложности доказательств в нижних оценках теории сложности).

$\mathsf{P} \neq \mathsf{NP}$$ZFC$$ZF$$PA$$PV$$PV$$\mathsf{P}$

$PV$$\mathsf{P} \neq \mathsf{NP}$

$PV$

$\mathsf{P} \neq \mathsf{NP}$$\mathsf{P}$