Alcance de la barrera de pruebas naturales

La barrera de las pruebas naturales de Razborov y Rudich establece que, bajo supuestos criptográficos creíbles, uno no puede esperar separar NP de P / poli al encontrar propiedades combinatorias de funciones que son constructivas, grandes y útiles. Hay varios resultados bien conocidos que logran evadir la barrera. También hay varios documentos que discuten posibles lagunas en las tres condiciones, como el resultado de que Chow muestra que la barrera es sensible a las violaciones débiles de la amplitud, y un artículo reciente de Chapman y Williamssugiriendo cómo evitar potencialmente la barrera relajando la condición de utilidad. Mi pregunta es si hay algún ejemplo, o incluso la posibilidad, de evitar la barrera de las pruebas naturales no violando la constructividad, la amplitud o la utilidad, sino cayendo completamente fuera de su alcance. Es decir, no es del todo obvio para mí por qué cada método potencial de prueba debería basarse en la búsqueda de "propiedades" combinatorias y luego en dividir todas las funciones en aquellas que cumplen y no cumplen con la propiedad. ¿Por qué este marco de operación debe aplicarse a todas las pruebas posibles, y si no es así, cómo serían otros tipos de pruebas?

$f: \{0,1\}^* \rightarrow \{0,1\}$$C$$f$$f \notin C$$f$$C$${\cal P}_f$

${\cal P}_f(f) = 1$${\cal P}_f(g) = 0$$g \neq f$

$f \notin C$${\cal P}_f$$C$

$f \in TIME[2^{O(n)}]$${\cal P}_f$$f$$E$$P/poly$$P/poly$

Entonces, Razborov y Rudich son más fundamentales de lo que podrías pensar inicialmente.

Tiene razón: el teorema de las pruebas naturales trata sobre las propiedades naturales (y solo de manera informal sobre las pruebas). El propio Razborov escribió dos documentos al mismo tiempo para analizar la clase de pruebas formales y límites inferiores de complejidad:

• Aritmética limitada y límites inferiores en la complejidad booleana , 1995
• Inestabilidad de límites más bajos en el tamaño del circuito en ciertos fragmentos de aritmética limitada , 1995

El primero estudia la formalización de las pruebas de límite inferior existentes en fragmentos débiles de aritmética (límites superiores en la dureza de la teoría de la complejidad de prueba límites inferiores).

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