Hispanopedia Wiki
Articulo de referencia

Conjetura de Berman-Hartmanis

Problema sin resolver en informática ¿Existe un isomorfismo en tiempo polinomial entre cada par de lenguajes NP-completos? Más problemas sin resolver en informática En la teoría...

Hispanopedia WikiContenido en espanolLectura gratuita
Problema sin resolver en informática
¿Existe un isomorfismo en tiempo polinomial entre cada par de lenguajes NP-completos?
Más problemas sin resolver en informática

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 . [ 1 ] De manera informal, afirma que todos los lenguajes NP-completos se parecen, en el sentido de que pueden relacionarse entre sí mediante isomorfismos de tiempo polinomial . [ 2 ] [ 3 ] [ 4 ] [ 5 ]

Declaraciones

Enunciado mediante p-isomorfismo

Un isomorfismo entre lenguajes formales L 1 y L 2 es una aplicación biyectiva 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 .

Un isomorfismo de tiempo polinomial, o p- isomorfismo para abreviar, es un isomorfismo f donde tanto f como su función inversa se pueden calcular en una cantidad de tiempo polinomial en las longitudes de sus argumentos.

Berman y Hartmanis conjeturaron que todos los lenguajes NP-completos son p-isomorfos entre sí. [ 1 ]

Declaración utilizando lenguajes rellenables

Un lenguaje formal L es rellenable si existe una función de tiempo polinomial f ( x , y ), con una inversa de tiempo polinomial, tal que para cada x y cada y , la cadena x pertenece a L si y solo 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. Berman y Hartmanis demostraron que todos los pares de lenguajes NP-completos rellenables son p-isomorfos. [ 1 ]

Dado que el p -isomorfismo preserva la capacidad de relleno, y existen lenguajes NP-completos con capacidad de relleno, una forma equivalente de enunciar la conjetura de Berman-Hartmanis es que todos los lenguajes NP-completos son con capacidad de relleno.

Declaración que utiliza relaciones de equivalencia

El isomorfismo en tiempo polinomial es una relación de equivalencia y puede usarse para dividir los lenguajes formales en clases de equivalencia , por lo que otra forma de enunciar la conjetura de Berman-Hartmanis es que los lenguajes NP-completos forman una única clase de equivalencia para esta relación.

Trascendencia

No existencia de lenguajes NP-completos dispersos

Un lenguaje formal se denomina disperso si el número de instancias de "sí" de longitud n crece únicamente de forma polinómica 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 un número exponencial de instancias de "sí", entonces no puede ser p- isomorfo a un lenguaje disperso, ya que sus instancias de "sí" tendrían que mapearse a cadenas de longitud superior a la polinómica para que el mapeo fuera biyectivo. Por lo tanto, si la conjetura de Berman-Hartmanis es cierta, una consecuencia inmediata sería la inexistencia de lenguajes NP-completos dispersos.

P vs. NP

La inexistencia de lenguajes NP-completos dispersos implica a su vez que P ≠ NP , porque si P = NP, entonces todo lenguaje no trivial en P (incluidos algunos dispersos, como el lenguaje de cadenas binarias cuyos bits son todos cero) sería NP-completo. En 1982, Steve Mahaney publicó su demostración de que la inexistencia de lenguajes NP-completos dispersos (con la NP-completitud definida de la manera estándar usando reducciones de muchos a 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-completitud usando reducciones de Turing , la existencia de un lenguaje NP-completo disperso implicaría un colapso inesperado de la jerarquía polinomial . [ 6 ]

Evidencia

Como evidencia a favor de la conjetura, Agrawal et al. (1997) demostraron que una conjetura análoga con un tipo restringido de reducción es verdadera: cada par de lenguajes que son completos para NP bajo reducciones muchos-uno AC 0 tienen un isomorfismo AC 0. [ 7 ] Agrawal y Watanabe (2009) demostraron que, si existen funciones unidireccionales que no pueden invertirse en tiempo polinomial en todas las entradas, pero si cada una de estas funciones tiene un subconjunto pequeño pero denso de entradas en las que puede invertirse en P/poly (como es cierto para las funciones conocidas de este tipo), entonces cada par de lenguajes NP-completos tienen un isomorfismo P/poly. [ 8 ] Y Fenner, Fortnow y Kurtz (1992) encontraron un modelo de máquina oráculo en el que el análogo a la conjetura del isomorfismo es verdadero. [ 9 ]

Joseph y Young (1985) y Kurtz, Mahaney y Royer (1995) aportaron pruebas en contra de la conjetura . Joseph y Young introdujeron una clase de problemas NP-completos, los conjuntos k -creativos , para los cuales no se conoce ningún p -isomorfismo a los problemas NP-completos estándar. [ 10 ] Kurtz et al. demostraron que en los modelos de máquinas oráculo con 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 conjuntos completos para NP A tienen 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 aleatorias, y la construcción de Kurtz et al. puede llevarse a cabo con dicha función en lugar del oráculo. Por esta razón, entre otras, muchos teóricos de la complejidad creen que la conjetura de isomorfismo de Berman-Hartmanis es falsa. [ 12 ]

Véase también

Referencias

  1. 1 2 3 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 , MR 0455536 .
  2. ↑ Rothe, Jörg (2005), "3.6.2 La conjetura de isomorfismo de Berman-Hartmanis y las funciones unidireccionales", Teoría de la complejidad y criptología: una introducción a la criptocomplejidad , Birkhäuser, pp. 108-114 , ISBN  978-3-540-22147-0.
  3. ↑ Schöning, Uwe; Pruim, Randall J. (1998), "15. La conjetura de Berman-Hartmanis y los conjuntos dispersos", Gems of Theoretical Computer Science , Springer, pp. 123-129 , ISBN  978-3-540-64425-5.
  4. ↑ Kurtz, Stuart; Mahaney, Steve; Royer, Jim ( 1990), "La estructura de los grados completos", Retrospectiva de la complejidad , Springer, págs. 108–146 
  5. ↑ 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, pp. 19–48 , ISBN  978-1-84816-245-7.
  6. ↑ 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 .
  7. ↑ Agrawal, Manindra ; Allender, Eric ; Impagliazzo, Russell ; Pitassi, Toniann ; Rudich, Steven (1997), "Reduciendo 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 , ISBN  0-89791-888-6, S2CID 14739803 . Agrawal, Manindra ; Allender, Eric ; Rudich, Steven (1998), "Reducciones en la complejidad de circuitos: 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.
  8. ↑ Agrawal, M. ; Watanabe, O. (2009), "Funciones unidireccionales y la conjetura de Berman-Hartmanis", 24.ª Conferencia Anual IEEE sobre Complejidad Computacional (PDF) , págs. 194-202 , doi : 10.1109/CCC.2009.17 , ISBN  978-0-7695-3717-7, S2CID 15244907 .
  9. ↑ Fenner, S.; Fortnow, L .; Kurtz, SA (1992), "La conjetura del isomorfismo se cumple en relación con un oráculo", Actas del 33.er 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 , ISBN   0-8186-2900-2, S2CID 36512284 .
  10. ↑ Joseph, Deborah ; Young, Paul (1985), "Algunas observaciones sobre las funciones testigo 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 .
  11. ↑ 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  .
  12. ↑ Fortnow, Lance (28 de marzo de 2003), La conjetura del isomorfismo de Berman-Hartmanis.