Escopo da barreira de provas naturais

A barreira das provas naturais de Razborov e Rudich afirma que, sob suposições criptográficas confiáveis, não se pode esperar separar NP de P / poly encontrando propriedades combinatórias de funções construtivas, grandes e úteis. Existem vários resultados bem conhecidos que conseguem escapar à barreira. Também existem vários artigos discutindo possíveis brechas nas três condições, como resultado de Chow mostrando que a barreira é sensível a violações fracas da grandeza, e um artigo recente de Chapman e Williamssugerindo como potencialmente evitar a barreira relaxando a condição de utilidade. Minha pergunta é se existem exemplos, ou mesmo a possibilidade, de evitar a barreira das provas naturais, não violando a construtividade, a grandeza ou a utilidade, mas ficando totalmente fora do seu escopo. Ou seja, não é absolutamente óbvio para mim o porquê de todo método potencial de prova precisar se basear na localização de "propriedades" combinatórias e no particionamento de todas as funções naquelas que atendem e não atendem à propriedade. Por que essa estrutura de operação se aplica a todas as provas possíveis e, se não, como seriam os outros tipos de provas?

Seja seja uma função e deixe C ser uma classe de algoritmos que trabalham em fatias finitas de f . Cada circuito limite inferior tudo o que é uma prova de que f ∉ C , para alguns f e alguns C . Considere a "propriedade combinatória das funções booleanas" P f , de modo que$f: \{0,1\}^* \rightarrow \{0,1\}$$C$$f$$f \notin C$$f$$C$${\cal P}_f$

e P f (g)=0para todos osg≠f.${\cal P}_f(f) = 1$${\cal P}_f(g) = 0$$g \neq f$

Uma prova de que é uma prova de que P f é útil contra C , na terminologia de Razborov e Rudich. Ou seja, "utilidade" é totalmente inevitável - não há como "ficar fora do seu escopo". Se você provou ser um limite inferior do circuito, forneceu algumas propriedades úteis.$f \notin C$${\cal P}_f$$C$

Note que, se , então P f também é construtivo, na terminologia de Razborov e Rudich. Assim, para as funções de f calculável dentro E , mas não no (por exemplo) P / p o l y , construtividade também se aplica a pelo menos uma propriedade de funções booleanas que é útil contra P / p o l y .$f \in TIME[2^{O(n)}]$${\cal P}_f$$f$$E$$P/poly$$P/poly$

Então, Razborov e Rudich são mais fundamentais do que você imagina inicialmente.

Você está certo: o teorema das provas naturais é sobre propriedades naturais (e apenas informalmente sobre provas). O próprio Razborov escreveu dois trabalhos na mesma época, analisando a classe de provas formais e os limites inferiores da complexidade:

• Aritmética limitada e limites inferiores na complexidade booleana , 1995
• Improvabilidade de limites inferiores no tamanho do circuito em certos fragmentos da aritmética limitada , 1995

O primeiro estuda a formalização de provas de limite inferior existentes em fragmentos aritméticos fracos (limites superiores na dureza de provar limites inferiores da teoria da complexidade).

$\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}$