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 tal prueba no puede usarse posiblemente para resolver el problema P vs. NP .
Descripción general
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 demuestran límites inferiores en la complejidad del circuito de las funciones booleanas . Una prueba natural muestra, directa o indirectamente, que una función booleana tiene 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 demostraciones no pueden separar ciertas clases de complejidad. Notablemente, asumiendo que existen funciones pseudoaleatorias, estas pruebas no pueden separar las clases de complejidad P y NP . [2]
Por ejemplo, su artículo dice:
- [...] considere una estrategia de prueba comúnmente concebida para probar P ≠ NP:
- Formular alguna noción matemática de "discrepancia" o "dispersión" o "variación" de los valores de una función booleana, o de un politopo asociado u otra estructura. [...]
- Demuestre mediante un argumento inductivo que los circuitos de tamaño polinómico sólo pueden calcular funciones de discrepancia "baja". [...]
- Luego demuestre que SAT , o alguna otra función en NP, tiene una discrepancia "alta".
- Nuestro teorema principal en la Sección 4 da evidencia de que ninguna estrategia de prueba en este sentido puede tener éxito.
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 tamaño 2 n de una función booleana de n entradas se da 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 comprender satisfagan esta condición. La condición de amplitud requiere que la propiedad se mantenga 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 una fuera del lenguaje de C . Una prueba natural, es una prueba de que establece que un determinado idioma mentiras 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ímite inferior contra clases C más pequeñas que P / poli 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 . Dan una fuerte evidencia de que las técnicas utilizadas en estas demostraciones no pueden extenderse para mostrar límites inferiores más fuertes. En particular, las pruebas naturales AC 0 no pueden ser útiles contra AC 0 [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 .
Existe una fuerte creencia actual de que el mecanismo de este documento en realidad bloquea las pruebas de límite inferior contra la clase de complejidad TC 0 de los circuitos de umbral de profundidad constante y tamaño polinomial, que se cree, pero no se ha demostrado, es más pequeño que P / poli. [3] Esta creencia se debe a que, según conjeturas ampliamente aceptadas sobre la dureza de la factorización en ciertos grupos de curvas elípticas , existen funciones pseudoaleatorias exponencialmente duras que se pueden calcular 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 propiedades duras o completas para el espacio exponencial. [5]
Notas
- ^ "Premio Gödel ACM-SIGACT 2007" . Archivado desde el original el 3 de marzo de 2016 . Consultado el 11 de agosto de 2014 .
- ^ AA Razborov y S. Rudich (1997). "Pruebas naturales". Revista de Ciencias de la Computación y Sistemas . 55 : 24–35. doi : 10.1006 / jcss.1997.1494 .( Borrador )
- ^ https://complexityzoo.net/Complexity_Zoo:T#tc0
- ^ http://dl.acm.org/citation.cfm?id=972643
- ^ K. Regan (octubre de 2002). "Comprender el enfoque de Mulmuley-Sohoni para P frente a NP" (PDF) . Boletín de la Asociación Europea de Informática Teórica . 78 : 86–97.
Referencias
- AA Razborov (2004). "Pruebas y cálculos factibles: asociación y fusión". Actas de la 31ª ICALP . Apuntes de conferencias en Ciencias de la Computación. 3142 . págs. 8-14.( Borrador )
- Lance Fortnow (10 de mayo de 2006). "La importancia de las pruebas naturales" .
- Chow, Timothy Y. (2011), "¿QUÉ ES ... una prueba natural?" (PDF) , Notices , AMS, 58 (11) , consultado el 5 de agosto de 2014