En la teoría de la complejidad computacional , una prueba natural es un cierto tipo de prueba que establece que una clase de complejidad difiere de otra. Si bien estas pruebas son en cierto sentido "naturales", se puede demostrar (asumiendo una conjetura ampliamente creída sobre la existencia de funciones pseudoaleatorias ) que ninguna prueba de este tipo puede usarse para resolver el problema P vs. NP .
La noción de pruebas naturales fue introducida por Alexander Razborov y Steven Rudich en su artículo "Pruebas naturales", presentado por primera vez en 1994 y publicado posteriormente en 1997, por el que recibieron el Premio Gödel 2007 . [1]
Específicamente, las pruebas naturales prueban los límites inferiores de la complejidad del circuito de las funciones booleanas . Una prueba natural muestra, directa o indirectamente, que una función booleana tiene una cierta propiedad combinatoria natural . Bajo el supuesto de que existen funciones pseudoaleatorias con "dureza exponencial" como se especifica en su teorema principal, Razborov y Rudich muestran que estas pruebas no pueden separar ciertas clases de complejidad. En particular, suponiendo que existan funciones pseudoaleatorias, estas pruebas no pueden separar las clases de complejidad P y NP . [2]
Una propiedad de las funciones booleanas se define como natural si contiene una propiedad que cumple las condiciones de constructividad y amplitud definidas por Razborov y Rudich. En términos generales, la condición de constructividad requiere que una propiedad sea decidible en tiempo (cuasi) polinomial cuando la tabla de verdad de 2 n de tamaño de una función booleana de entrada n se proporciona como entrada, asintóticamente a medida que n aumenta . Esto es lo mismo que el tiempo exponencial simple en n . Es probable que las propiedades que son fáciles de entender satisfagan esta condición. La condición de amplitud requiere que la propiedad se cumpla para una fracción suficientemente grande del conjunto de todas las funciones booleanas.
Una propiedad es útil contra una clase de complejidad C si cada secuencia de funciones booleanas que tienen la propiedad define infinitamente a menudo un lenguaje fuera de C . Una prueba natural es una prueba que establece que cierto lenguaje se encuentra fuera de C y se refiere a una propiedad natural que es útil contra C.
Razborov y Rudich dan una serie de ejemplos de pruebas de límite inferior contra las clases C más pequeñas que P/poly que pueden "naturalizarse", es decir, convertirse en pruebas naturales. Un ejemplo importante trata las pruebas de que el problema de paridad no está en la clase AC 0 . Proporcionan una fuerte evidencia de que las técnicas utilizadas en estas demostraciones no pueden extenderse para mostrar cotas inferiores más fuertes. En particular, las pruebas naturales AC 0 no pueden ser útiles contra AC 0 [m] .