En la teoría de la complejidad computacional , una prueba natural es un 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 aceptada sobre la existencia de funciones pseudoaleatorias ) que no es posible utilizar una prueba de este tipo 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]
En concreto, las pruebas naturales demuestran límites inferiores en la complejidad del circuito de funciones booleanas . Una prueba natural muestra, ya sea 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 existen funciones pseudoaleatorias, estas pruebas no pueden separar las clases de complejidad P y NP. [2]
Por ejemplo, su artículo dice:
Una propiedad de funciones booleanas se define como natural si contiene una propiedad que cumple con las condiciones de constructividad y grandeza 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 tamaño 2 n de una función booleana de n entradas 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 grandeza 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 infinitamente a menudo define un lenguaje fuera de C. Una prueba natural es una prueba que establece que un determinado lenguaje se encuentra fuera de C y se refiere a una propiedad natural que es útil contra C.
Razborov y Rudich dan varios ejemplos de pruebas de límites inferiores contra clases C más pequeñas que P/poly que pueden ser "naturalizadas", es decir, convertidas en pruebas naturales. Un ejemplo importante trata de las pruebas de que el problema de paridad no está en la clase AC 0 . Proporcionan evidencia sólida de que las técnicas utilizadas en estas pruebas no pueden extenderse para mostrar límites inferiores más fuertes. En particular, las pruebas naturales de AC 0 no pueden ser útiles contra AC0[m].
Razborov y Rudich también reproducen la prueba incondicional de Avi Wigderson de que las pruebas naturales no pueden demostrar límites inferiores exponenciales para el problema del logaritmo discreto .
Actualmente, existe una fuerte creencia de que el mecanismo de este artículo en realidad bloquea las pruebas de límite inferior contra la clase de complejidad TC 0 de circuitos de umbral de tamaño polinomial y profundidad constante, que se cree, pero no se ha demostrado, que es menor que P/poly. [3] Esta creencia se debe a que , según conjeturas ampliamente aceptadas sobre la dificultad de factorizar en ciertos grupos de curvas elípticas , existen funciones pseudoaleatorias exponencialmente difíciles computables en TC 0. [4] Sin embargo, algunos investigadores creen que las limitaciones de Razborov-Rudich son en realidad una buena guía para lo que podría implicar una prueba de límite inferior "sobrenatural", como las propiedades difíciles o completas para el espacio exponencial. [5]