¿Existe un isomorfismo de tiempo polinomial entre cada dos lenguajes NP-completos?
En la teoría de la complejidad estructural , la conjetura de Berman-Hartmanis es una conjetura sin resolver que lleva el nombre de Leonard C. Berman y Juris Hartmanis que establece que todos los lenguajes NP-completos se parecen, en el sentido de que pueden relacionarse entre sí mediante isomorfismos de tiempo polinomial . [1] [2] [3] [4]
Declaración
Un isomorfismo entre los lenguajes formales L 1 y L 2 es un mapa biyectivo f de cadenas en el alfabeto de L 1 a cadenas en el alfabeto de L 2 , con la propiedad de que una cadena x pertenece a L 1 si y solo si f ( x ) pertenece a L 2 . Es un isomorfismo de tiempo polinomial (o p -isomorfismo para abreviar) si tanto f como su función inversa pueden calcularse en una cantidad de polinomio de tiempo en la longitud de sus argumentos.
Berman y Hartmanis (1977) observaron que todos los lenguajes conocidos en ese momento como NP-completos eran p -isomórficos. Más fuertemente, observaron que todos los lenguajes NP-completos conocidos en ese momento eran fáciles de usar , y demostraron (de manera análoga al teorema del isomorfismo de Myhill ) que todos los pares de lenguajes NP completos que se pueden completar son p -isomórficos. Un lenguaje L es paddable si hay una función de tiempo polinomio f ( x , y ) con un tiempo inverso polinomio y con la propiedad de que, a pesar de x y y , x pertenece a L si y sólo si f ( x , y ) pertenece a L : es decir, es posible rellenar la entrada x con información irrelevante y , de forma invertible, sin cambiar su pertenencia al lenguaje. Con base en estos resultados, Berman y Hartmanis conjeturaron que todos los lenguajes NP-completos son p -isomórficos. [5]
Dado que el p -isomorfismo preserva la capacidad de relleno, y existen lenguajes NP-completos que se pueden rellenar, una forma equivalente de enunciar la conjetura de Berman-Hartmanis es que todos los lenguajes NP-completos se pueden rellenar. El isomorfismo polinomial del tiempo es una relación de equivalencia , y puede usarse para dividir los lenguajes formales en clases de equivalencia , por lo que otra forma de plantear la conjetura de Berman-Hartmanis es que los lenguajes NP-completos forman una sola clase de equivalencia para esta relación.
Trascendencia
Si la conjetura de Berman-Hartmanis es cierta, una consecuencia inmediata sería la inexistencia de lenguajes NP completos dispersos , es decir, lenguajes en los que el número de instancias sí de longitud n crece sólo polinomialmente en función de n . Los lenguajes NP-completos conocidos tienen un número de instancias de sí que crece exponencialmente, y si L es un lenguaje con muchas instancias de sí exponencialmente, entonces no puede ser p -isomórfico para un lenguaje disperso, porque sus instancias de sí tendrían que ser mapeado a cadenas que son más que polinomialmente largas para que el mapeo sea uno a uno.
La inexistencia de lenguajes NP completos dispersos a su vez implica que P ≠ NP , porque si P = NP entonces todos los lenguajes no triviales en P (incluidos algunos dispersos, como el lenguaje de cadenas binarias cuyos bits son cero) serían NP -completo. En 1982, Steve Mahaney publicó su prueba de que la inexistencia de lenguajes NP-completos dispersos (con NP-completitud definida de la manera estándar usando reducciones muchos-uno ) es de hecho equivalente a la afirmación de que P ≠ NP; este es el teorema de Mahaney . Incluso para una definición relajada de NP-completo usando reducciones de Turing , la existencia de un lenguaje NP-completo escaso implicaría un colapso inesperado de la jerarquía polinomial . [6]
Evidencia
Como evidencia de la conjetura, Agrawal et al. (1997) mostró que una conjetura análoga con un tipo restringido de reducción es cierta: cada dos idiomas que están completos para NP bajo AC 0 reducciones muchos-uno tienen un isomorfismo AC 0 . [7] Agrawal y Watanabe (2009) demostraron que, si existen funciones unidireccionales que no se pueden invertir en tiempo polinomial en todas las entradas, pero si cada función tiene un subconjunto pequeño pero denso de entradas en las que se puede invertir en P / poli (como es cierto para las funciones conocidas de este tipo), entonces cada dos lenguajes NP-completos tienen un P / poli isomorfismo. [8] Y Fenner, Fortnow y Kurtz (1992) encontraron un modelo de máquina de oráculo en el que el análogo a la conjetura del isomorfismo es verdadero. [9]
Joseph & Young (1985) y Kurtz, Mahaney & Royer (1995) proporcionaron pruebas contra la conjetura . Joseph y Young presentaron una clase de problemas NP-completos, los k -conjuntos creativos , para los que no se conoce ningún p -isomorfismo con respecto a los problemas NP-completos estándar. [10] Kurtz y col. mostró que en la máquina modelos oráculo dado acceso a un oráculo aleatorio , el análogo de la conjetura no es cierto: si A es un oráculo aleatorio, entonces no todos los juegos completos para NP A tener isomorfismos en P A . [11] Los oráculos aleatorios se utilizan comúnmente en la teoría de la criptografía para modelar funciones hash criptográficas que son computacionalmente indistinguibles de las aleatorias, y la construcción de Kurtz et al. se puede llevar a cabo con tal función en lugar del oráculo. Por esta razón, entre otras, muchos teóricos de la complejidad creen que la conjetura del isomorfismo de Berman-Hartmanis es falsa. [12]
Referencias
- ^ Rothe, Jörg (2005), "3.6.2 La conjetura del isomorfismo de Berman-Hartmanis y funciones unidireccionales ", Teoría de la complejidad y criptología: una introducción a la criptocomplejidad , Birkhäuser, págs. 108-114, ISBN 978-3-540-22147-0.
- ^ Schöning, Uwe; Pruim, Randall J. (1998), "15. La conjetura de Berman-Hartmanis y los conjuntos dispersos", Gems of Theoretical Computer Science , Springer, págs. 123-129, ISBN 978-3-540-64425-5.
- ^ Kurtz, Stuart; Mahaney, Steve; Royer, Jim (1990), "La estructura de los grados completos", Complexity Retrospective , Springer, págs. 108-146
- ^ Agrawal, Manindra (2011), "La conjetura del isomorfismo para NP", en Cooper, S. Barry; Sorbi, Andrea (eds.), Computabilidad en contexto: Computación y lógica en el mundo real (PDF) , World Scientific, págs. 19–48, ISBN 978-1-84816-245-7.
- ^ Berman, L .; Hartmanis, J. (1977), "Sobre isomorfismos y densidad de NP y otros conjuntos completos" (PDF) , SIAM Journal on Computing , 6 (2): 305–322, doi : 10.1137 / 0206023 , hdl : 1813/7101 , Señor 0455536.
- ^ Mahaney, Stephen R. (1982), "Conjuntos completos dispersos para NP: solución de una conjetura de Berman y Hartmanis", Journal of Computer and System Sciences , 25 (2): 130-143, doi : 10.1016 / 0022-0000 ( 82) 90002-2 , HDL : 1813/6257 , MR 0680515.
- ^ Agrawal, Manindra ; Allender, Eric ; Impagliazzo, Russell ; Pitassi, Toniann ; Rudich, Steven (1997), "Reducir la complejidad de las reducciones", Actas del 29º Simposio ACM sobre Teoría de la Computación (STOC '97) , págs. 730–738, doi : 10.1145 / 258533.258671 , S2CID 14739803. Agrawal, Manindra ; Allender, Eric ; Rudich, Steven (1998), "Reducciones en la complejidad del circuito: un teorema de isomorfismo y un teorema de brecha", Journal of Computer and System Sciences , 57 (2): 127-143, doi : 10.1006 / jcss.1998.1583.
- ^ Agrawal, M .; Watanabe, O. (2009), "Funciones unidireccionales y la conjetura de Berman-Hartmanis", 24a Conferencia anual del IEEE sobre complejidad computacional (PDF) , págs. 194–202, doi : 10.1109 / CCC.2009.17 , S2CID 15244907.
- ^ Fenner, S .; Fortnow, L .; Kurtz, SA (1992), "La conjetura del isomorfismo es válida en relación con un oráculo", Actas del 33º Simposio anual del IEEE sobre fundamentos de la informática , págs. 30–39, CiteSeerX 10.1.1.42.6130 , doi : 10.1109 / SFCS. 1992.267821 , S2CID 36512284.
- ^ Joseph, Deborah ; Young, Paul (1985), "Algunas observaciones sobre las funciones de testigos para conjuntos no polinomiales y no completos en NP" , Theoretical Computer Science , 39 (2-3): 225-237, doi : 10.1016 / 0304-3975 (85) 90140-9 , MR 0821203.
- ^ Kurtz, Stuart A .; Mahaney, Stephen R .; Royer, James S. (1995), "La conjetura del isomorfismo falla en relación con un oráculo aleatorio" , Journal of the ACM , 42 (2): 401–420, doi : 10.1145 / 201019.201030 , MR 1409741 , S2CID 52152959.
- ^ Fortnow, Lance (28 de marzo de 2003), La conjetura del isomorfismo de Berman-Hartmanis.