Supuesto de dureza computacional
Hipótesis en la teoría de la complejidad computacional

En la teoría de la complejidad computacional , un supuesto de dureza computacional es la hipótesis de que un problema particular no se puede resolver de manera eficiente (donde eficientemente generalmente significa "en tiempo polinomial "). No se sabe cómo demostrar la dureza (incondicional) para esencialmente cualquier problema útil. En cambio, los científicos informáticos se basan en reducciones para relacionar formalmente la dureza de un problema nuevo o complicado con un supuesto de dureza computacional sobre un problema que se entiende mejor.

Los supuestos de dureza computacional son de particular importancia en criptografía . Un objetivo principal en criptografía es crear primitivas criptográficas con seguridad demostrable . En algunos casos, se descubre que los protocolos criptográficos tienen seguridad teórica de la información ; el bloc de notas de un solo uso es un ejemplo común. Sin embargo, la seguridad teórica de la información no siempre se puede lograr; en tales casos, los criptógrafos recurren a la seguridad computacional. En términos generales, esto significa que estos sistemas son seguros suponiendo que cualquier adversario esté limitado computacionalmente , como lo están todos los adversarios en la práctica.

Las suposiciones de dureza computacional también son útiles para guiar a los diseñadores de algoritmos : es poco probable que un algoritmo simple refute una suposición de dureza computacional bien estudiada como P ≠ NP .

Comparación de supuestos de dureza

Los científicos informáticos tienen diferentes formas de evaluar qué supuestos de dureza son más confiables.

Supuestos de resistencia a la dureza

Decimos que una suposición es más fuerte que otra cuando implica (y lo inverso es falso o no se sabe). En otras palabras, incluso si la suposición fuera falsa, la suposición podría seguir siendo verdadera y los protocolos criptográficos basados ​​en suposiciones podrían seguir siendo seguros de usar. Por lo tanto, cuando se diseñan protocolos criptográficos, se espera poder demostrar la seguridad utilizando las suposiciones más débiles posibles. A {\estilo de visualización A} B {\estilo de visualización B} A {\estilo de visualización A} B {\estilo de visualización B} A {\estilo de visualización A} B {\estilo de visualización B} B {\estilo de visualización B}

Supuestos de caso promedio vs. supuestos de caso peor

Una suposición de caso promedio dice que un problema específico es difícil en la mayoría de las instancias de alguna distribución explícita, mientras que una suposición de peor caso solo dice que el problema es difícil en algunas instancias. Para un problema dado, la dureza del caso promedio implica la dureza del peor caso, por lo que una suposición de dureza del caso promedio es más fuerte que una suposición de dureza del peor caso para el mismo problema. Además, incluso para problemas incomparables, una suposición como la Hipótesis del Tiempo Exponencial a menudo se considera preferible a una suposición de caso promedio como la conjetura de la camarilla plantada . [1] Sin embargo, para aplicaciones criptográficas, saber que un problema tiene alguna instancia difícil (el problema es difícil en el peor de los casos) es inútil porque no nos proporciona una forma de generar instancias difíciles. [2] Afortunadamente, muchas suposiciones de caso promedio utilizadas en criptografía (incluidos RSA, logaritmo discreto y algunos problemas de celosía) pueden basarse en suposiciones del peor de los casos a través de reducciones del peor de los casos al caso promedio. [3]

Falsabilidad

Una característica deseada de un supuesto de dureza computacional es la falsabilidad , es decir, que si el supuesto fuera falso, entonces sería posible probarlo. En particular, Naor (2003) introdujo una noción formal de falsabilidad criptográfica. [4] En términos generales, se dice que un supuesto de dureza computacional es falsable si puede formularse en términos de un desafío: un protocolo interactivo entre un adversario y un verificador eficiente, donde un adversario eficiente puede convencer al verificador de aceptar si y solo si el supuesto es falso.

Supuestos comunes de dureza criptográfica

Existen muchas suposiciones de dureza criptográfica en uso. Esta es una lista de algunas de las más comunes y algunos protocolos criptográficos que las utilizan.

Factorización de números enteros

Dado un entero compuesto , y en particular uno que es el producto de dos primos grandes , el problema de factorización de enteros es encontrar y (más generalmente, encontrar primos tales que ). Es un problema abierto importante encontrar un algoritmo para la factorización de enteros que se ejecute en tiempo polinomial en el tamaño de representación ( ). La seguridad de muchos protocolos criptográficos se basa en el supuesto de que la factorización de enteros es difícil (es decir, no se puede resolver en tiempo polinomial). Los criptosistemas cuya seguridad es equivalente a este supuesto incluyen el criptosistema Rabin y el criptosistema Okamoto-Uchiyama . Muchos más criptosistemas se basan en supuestos más fuertes como RSA, problemas de residuosidad y ocultamiento de Phi. norte {\estilo de visualización n} norte = pag ⋅ q {\displaystyle n=p\cdot q} pag {\estilo de visualización p} q {\estilo de visualización q} pag 1 , … , pag a {\displaystyle p_{1},\puntos ,p_{k}} norte = ∏ i pag i {\displaystyle n=\prod_{i}p_{i}} registro ⁡ norte {\displaystyle \log n}

Problema de RSA

Dado un número compuesto , exponente y número , el problema RSA consiste en encontrar . Se supone que el problema es difícil, pero se vuelve fácil dada la factorización de . En el criptosistema RSA , es la clave pública , es el cifrado del mensaje y la factorización de es la clave secreta utilizada para el descifrado. norte {\estilo de visualización n} mi {\estilo de visualización e} do := metro mi ( metro o d norte ) {\displaystyle c:=m^{e}(\mathrm {mod} \;n)} metro {\estilo de visualización m} norte {\estilo de visualización n} ( norte , mi ) {\estilo de visualización (n,e)} do {\estilo de visualización c} metro {\estilo de visualización m} norte {\estilo de visualización n}

Problemas de residualidad

Dado un número compuesto y enteros , el problema de residuosidad es determinar si existe (alternativamente, encontrar un) tal que norte {\estilo de visualización n} y , d {\estilo de visualización y,d} incógnita {\estilo de visualización x}

incógnita d ≡ y ( modificación norte ) . {\displaystyle x^{d}\equiv y{\pmod {n}}.}

Entre los casos especiales importantes se incluyen el problema de residuosidad cuadrática y el problema de residuosidad compuesta decisional . Como en el caso de RSA, se supone que este problema (y sus casos especiales) son difíciles, pero se vuelven fáciles dada la factorización de . Algunos criptosistemas que dependen de la dificultad de los problemas de residuosidad incluyen: norte {\estilo de visualización n}

Suposición de ocultamiento de Phi

Para un número compuesto , no se sabe cómo calcular de manera eficiente su función totiente de Euler . La suposición de ocultamiento de Phi postula que es difícil calcular , y además, incluso calcular cualquier factor primo de es difícil. Esta suposición se utiliza en el protocolo PIR de Cachin–Micali–Stadler . [5] metro {\estilo de visualización m} ϕ ( metro ) {\displaystyle \phi (m)} ϕ ( metro ) {\displaystyle \phi (m)} ϕ ( metro ) {\displaystyle \phi (m)}

Problema de registro discreto (DLP)

Dados los elementos y de un grupo , el problema del logaritmo discreto pide un entero tal que . No se sabe que el problema del logaritmo discreto sea comparable a la factorización de enteros, pero sus complejidades computacionales están estrechamente relacionadas . a {\estilo de visualización a} b {\estilo de visualización b} GRAMO {\estilo de visualización G} a {\estilo de visualización k} a = b a {\displaystyle a=b^{k}}

La mayoría de los protocolos criptográficos relacionados con el problema del logaritmo discreto se basan en realidad en el supuesto más fuerte de Diffie-Hellman : dados los elementos del grupo , donde es un generador y son números enteros aleatorios, es difícil encontrar . Entre los ejemplos de protocolos que utilizan este supuesto se incluyen el intercambio de claves Diffie-Hellman original , así como el cifrado ElGamal (que se basa en la variante aún más fuerte de Diffie-Hellman decisional (DDH) ). gramo , gramo a , gramo b {\displaystyle g,g^{a},g^{b}} gramo {\estilo de visualización g} a , b {\estilo de visualización a,b} gramo a ⋅ b {\displaystyle g^{a\cdot b}}

Mapas multilineales

Un mapa multilineal es una función (donde son grupos ) tal que para cualquier y , mi : GRAMO 1 , … , GRAMO norte → GRAMO yo {\displaystyle e:G_{1},\puntos ,G_{n}\rightarrow G_{T}} GRAMO 1 , … , GRAMO norte , GRAMO yo {\displaystyle G_{1},\dots ,G_{n},G_{T}} g 1 , … , g n ∈ G 1 , … G n {\displaystyle g_{1},\dots ,g_{n}\in G_{1},\dots G_{n}} a 1 , … , a n {\displaystyle a_{1},\dots ,a_{n}}

e ( g 1 a 1 , … , g n a n ) = e ( g 1 , … , g n ) a 1 ⋯ a n {\displaystyle e(g_{1}^{a_{1}},\dots ,g_{n}^{a_{n}})=e(g_{1},\dots ,g_{n})^{a_{1}\cdots a_{n}}} .

Para aplicaciones criptográficas, uno quisiera construir grupos y un mapa tales que las operaciones del mapa y del grupo puedan calcularse eficientemente, pero el problema del logaritmo discreto sigue siendo difícil. [6] Algunas aplicaciones requieren suposiciones más fuertes, por ejemplo, análogos multilineales de las suposiciones de Diffie-Hellman. G 1 , … , G n , G T {\displaystyle G_{1},\dots ,G_{n},G_{T}} e {\displaystyle e} G 1 , … , G n , G T {\displaystyle G_{1},\dots ,G_{n},G_{T}} G 1 , … , G n {\displaystyle G_{1},\dots ,G_{n}}

Para el caso especial de , se han construido mapas bilineales con seguridad creíble utilizando emparejamiento de Weil y emparejamiento de Tate . [7] En los últimos años se han propuesto muchas construcciones, pero muchas de ellas también se han roto, y actualmente no hay consenso sobre un candidato seguro. [8] n = 2 {\displaystyle n=2} n > 2 {\displaystyle n>2}

Algunos criptosistemas que se basan en supuestos de dureza multilineal incluyen:

Problemas de celosía

El problema computacional más fundamental en los retículos es el problema del vector más corto (SVP) : dado un retículo , encuentre el vector distinto de cero más corto . La mayoría de los criptosistemas requieren suposiciones más sólidas en las variantes del SVP, como el problema de los vectores independientes más cortos (SIVP) , GapSVP [10] o Unique-SVP [11] . L {\displaystyle L} v ∈ L {\displaystyle v\in L}

La suposición de dureza de red más útil en criptografía es para el problema de aprendizaje con errores (LWE): dadas muestras de , donde para alguna función lineal , es fácil aprender usando álgebra lineal . En el problema LWE, la entrada al algoritmo tiene errores, es decir, para cada par con una pequeña probabilidad . Se cree que los errores hacen que el problema sea intratable (para parámetros apropiados); en particular, existen reducciones conocidas del peor caso al caso promedio a partir de variantes de SVP. [12] ( x , y ) {\displaystyle (x,y)} y = f ( x ) {\displaystyle y=f(x)} f ( ⋅ ) {\displaystyle f(\cdot )} f ( ⋅ ) {\displaystyle f(\cdot )} y ≠ f ( x ) {\displaystyle y\neq f(x)}

Para las computadoras cuánticas , los problemas de factorización y logaritmo discreto son fáciles, pero se conjetura que los problemas de red son difíciles. [13] Esto hace que algunos criptosistemas basados ​​en red sean candidatos para la criptografía post-cuántica .

Algunos criptosistemas que se basan en la dureza de los problemas de red incluyen:

Supuestos de dureza no criptográfica

Además de sus aplicaciones criptográficas, los supuestos de dureza se utilizan en la teoría de la complejidad computacional para proporcionar evidencia de enunciados matemáticos que son difíciles de probar incondicionalmente. En estas aplicaciones, se demuestra que el supuesto de dureza implica algún enunciado teórico de la complejidad deseado, en lugar de demostrar que el enunciado es en sí mismo verdadero. El supuesto más conocido de este tipo es el supuesto de que P ≠ NP , [14] pero otros incluyen la hipótesis del tiempo exponencial , [15] la conjetura de la camarilla plantada y la conjetura de los juegos únicos . [16]

do-problemas difíciles

Se sabe que muchos problemas computacionales en el peor de los casos son difíciles o incluso completos para alguna clase de complejidad , en particular NP-hard (pero a menudo también PSPACE-hard , PPAD-hard , etc.). Esto significa que son al menos tan difíciles como cualquier problema de la clase . Si un problema es -hard (con respecto a las reducciones de tiempo polinomial), entonces no se puede resolver mediante un algoritmo de tiempo polinomial a menos que el supuesto de dificultad computacional sea falso. C {\displaystyle C} C {\displaystyle C} C {\displaystyle C} P ≠ C {\displaystyle P\neq C}

Hipótesis del tiempo exponencial (ETH) y variantes

La hipótesis del tiempo exponencial (ETH) es un fortalecimiento de la hipótesis de dureza, que conjetura que no solo el problema de satisfacibilidad booleano (SAT) no tiene un algoritmo de tiempo polinomial, sino que además requiere tiempo exponencial ( ). [17] Una hipótesis aún más fuerte, conocida como la hipótesis del tiempo exponencial fuerte (SETH) conjetura que -SAT requiere tiempo, donde . ETH, SETH y las suposiciones de dureza computacional relacionadas permiten deducir resultados de complejidad de grano fino, por ejemplo, resultados que distinguen el tiempo polinomial y el tiempo cuasipolinomial , [1] o incluso frente a . [18] Dichas suposiciones también son útiles en la complejidad parametrizada . [19] P ≠ N P {\displaystyle P\neq NP} 2 Ω ( n ) {\displaystyle 2^{\Omega (n)}} k {\displaystyle k} 2 ( 1 − ε k ) n {\displaystyle 2^{(1-\varepsilon _{k})n}} lim k → ∞ ε k = 0 {\displaystyle \lim _{k\rightarrow \infty }\varepsilon _{k}=0} n 1.99 {\displaystyle n^{1.99}} n 2 {\displaystyle n^{2}}

Supuestos de dureza del caso promedio

Se supone que algunos problemas computacionales son difíciles en promedio sobre una distribución particular de instancias. Por ejemplo, en el problema de la camarilla plantada , la entrada es un gráfico aleatorio muestreado, muestreando un gráfico aleatorio de Erdős–Rényi y luego "plantando" una -clique aleatoria, es decir, conectando nodos uniformemente aleatorios (donde ), y el objetivo es encontrar la -clique plantada (que es única whp). [20] Otro ejemplo importante es la Hipótesis de Feige , que es una suposición de dureza computacional sobre instancias aleatorias de 3-SAT (muestreadas para mantener una proporción específica de cláusulas a variables). [21] Las suposiciones de dureza computacional de caso promedio son útiles para probar la dureza de caso promedio en aplicaciones como las estadísticas, donde hay una distribución natural sobre las entradas. [22] Además, el supuesto de dureza de camarilla plantada también se ha utilizado para distinguir entre la complejidad temporal del peor caso polinomial y cuasi-polinomial de otros problemas, [23] de manera similar a la Hipótesis del Tiempo Exponencial. k {\displaystyle k} k {\displaystyle k} 2 log 2 ⁡ n ≪ k ≪ n {\displaystyle 2\log _{2}n\ll k\ll {\sqrt {n}}} k {\displaystyle k}

Juegos únicos

El problema de cobertura de etiqueta única es un problema de satisfacción de restricciones, donde cada restricción involucra dos variables , y para cada valor de hay un valor único de que satisface . Determinar si se pueden satisfacer todas las restricciones es fácil, pero la Conjetura del Juego Único (UGC) postula que determinar si se pueden satisfacer casi todas las restricciones ( -fracción, para cualquier constante ) o casi ninguna de ellas ( -fracción) es NP-difícil. [16] A menudo se sabe que los problemas de aproximación son NP-difíciles suponiendo UGC; dichos problemas se conocen como UG-difíciles. En particular, suponiendo UGC hay un algoritmo de programación semidefinida que logra garantías de aproximación óptimas para muchos problemas importantes. [24] C {\displaystyle C} x , y {\displaystyle x,y} x {\displaystyle x} y {\displaystyle y} C {\displaystyle C} ( 1 − ε ) {\displaystyle (1-\varepsilon )} ε > 0 {\displaystyle \varepsilon >0} ε {\displaystyle \varepsilon }

Ampliación de conjunto pequeño

Estrechamente relacionado con el problema de la cobertura de etiqueta única está el problema de expansión de conjuntos pequeños (SSE) : dado un grafo , encuentre un conjunto pequeño de vértices (de tamaño ) cuya expansión de aristas sea mínima. Se sabe que si SSE es difícil de aproximar, entonces también lo es la cobertura de etiqueta única. Por lo tanto, la hipótesis de expansión de conjuntos pequeños , que postula que SSE es difícil de aproximar, es una suposición más fuerte (pero estrechamente relacionada) que la conjetura del juego único. [25] Se sabe que algunos problemas de aproximación son SSE-hard [26] (es decir, al menos tan difíciles como aproximar SSE). G = ( V , E ) {\displaystyle G=(V,E)} n / log ⁡ ( n ) {\displaystyle n/\log(n)}

La conjetura 3SUM

Dado un conjunto de números, el problema 3SUM pregunta si existe un triplete de números cuya suma sea cero. Existe un algoritmo de tiempo cuadrático para 3SUM, y se ha conjeturado que ningún algoritmo puede resolver 3SUM en "tiempo verdaderamente subcuadrático": la conjetura 3SUM es la suposición de dureza computacional de que no existen algoritmos de tiempo cuadrático para 3SUM (para cualquier constante ). Esta conjetura es útil para probar límites inferiores casi cuadráticos para varios problemas, principalmente de geometría computacional . [27] n {\displaystyle n} O ( n 2 − ε ) {\displaystyle O(n^{2-\varepsilon })} ε > 0 {\displaystyle \varepsilon >0}

Véase también

Referencias

  1. ^ ab Braverman, Mark ; Ko, Young Kun; Weinstein, Omri (2015). "Aproximar el mejor equilibrio de Nash en tiempo - rompe la hipótesis del tiempo exponencial". Simposio sobre algoritmos discretos (SODA) . Sociedad de Matemáticas Industriales y Aplicadas . págs. 970–982. doi :10.1137/1.9781611973730.66. ISBN n o ( log ⁡ ( n ) ) {\displaystyle n^{o(\log(n))}}  978-1-61197-374-7.
  2. ^ J. Katz e Y. Lindell, Introducción a la criptografía moderna (Serie de criptografía y seguridad de redes Chapman y Hall/CRC), Chapman y Hall/CRC, 2007.
  3. ^ Goldwasser, Shafi ; Kalai, Yael Tauman (2016). "Supuestos criptográficos: un documento de posición". Conferencia sobre teoría de la criptografía (TCC) 2016 . Springer. págs. doi : 10.1007/978-3-662-49096-9_21 .
  4. ^ Naor, Moni (2003). "Sobre supuestos y desafíos criptográficos". En Boneh, Dan (ed.). Avances en criptología – CRYPTO 2003: 23.ª Conferencia anual internacional sobre criptología, Santa Bárbara, California, EE. UU., 17-21 de agosto de 2003, Actas . Notas de clase en informática. Vol. 2729. Berlín: Springer. págs. 96–109. doi : 10.1007/978-3-540-45146-4_6 . MR  2093188.
  5. ^ Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). "Recuperación de información privada computacional con comunicación polilogarítmica". En Stern, Jacques (ed.). Avances en criptología — EUROCRYPT '99 . Apuntes de clase en informática. Vol. 1592. Springer. págs. 402–414. doi :10.1007/3-540-48910-X_28. ISBN 978-3-540-65889-4.S2CID29690672  .​
  6. ^ Boneh, Dan ; Silverberg, Alice (2002). "Aplicaciones de formas multilineales a la criptografía". Archivo de ePrints de criptología .
  7. ^ Dutta, Ratna; Barúa, Rana; Sarkar, Palash (2004). "Protocolos criptográficos basados ​​en emparejamiento: una encuesta". Archivo ePrint de criptología .
  8. ^ Albrecht, Martin R. "¿Ya se rompió el sistema de codificación gradual?" . Consultado el 22 de marzo de 2018 .
  9. ^ Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2016). "Ofuscación de indistinguibilidad de candidatos y cifrado funcional para todos los circuitos" (PDF) . Revista SIAM sobre informática . 45 (3). SIAM: 882–929. doi :10.1137/14095772X.
  10. ^ Peikert, Chris (2009). "Sistemas criptográficos de clave pública a partir del problema del vector más corto en el peor de los casos: resumen ampliado". Actas del 41.º Simposio anual de la ACM sobre teoría de la computación (STOC) . págs. 333–342. doi :10.1145/1536414.1536461.
  11. ^ Ajtai, Miklós ; Dwork, Cynthia (1997). "Un criptosistema de clave pública con equivalencia de peor caso/caso promedio". Actas del 29.° Simposio anual de la ACM sobre teoría de la computación (STOC) . págs. 284–293. doi :10.1145/258533.258604.
  12. ^ Regev, Oded (2010). "El problema del aprendizaje con errores (encuesta por invitación)". Conferencia sobre complejidad computacional (CCC) 2010. págs. 191–204. doi :10.1109/CCC.2010.26.
  13. ^ Peikert, Chris (2016). "Una década de criptografía en red". Fundamentos y tendencias en informática teórica . 10 (4): 283–424. doi :10.1561/0400000074.
  14. ^ Fortnow, Lance (2009). "El estado del problema P versus NP" (PDF) . Comunicaciones de la ACM . 52 (9): 78–86. doi :10.1145/1562164.1562186. S2CID  5969255. Archivado desde el original (PDF) el 24 de febrero de 2011..
  15. ^ Woeginger, Gerhard (2003). "Algoritmos exactos para problemas NP-hard: una encuesta". Optimización combinatoria: ¡Eureka, te encoges! . Vol. 2570. Springer-Verlag. págs. 185–207. doi :10.1007/3-540-36478-1_17. S2CID  289357..
  16. ^ ab Khot, Subhash (2010). "Sobre la conjetura de los juegos únicos". Proc. 25.ª Conferencia IEEE sobre complejidad computacional (PDF) . págs. 99–121. doi :10.1109/CCC.2010.19..
  17. ^ Impagliazzo, Russell ; Paturi, Ramamohan (1999). "La complejidad de k-SAT". Actas de la 14.ª Conferencia IEEE sobre complejidad computacional . págs. 237–240. doi :10.1109/CCC.1999.766282.
  18. ^ Abboud, Amir; Vassilevska-Williams, Virginia ; Weimann, Oren (2014). "Consecuencias de una alineación más rápida de secuencias". Autómatas, lenguajes y programación - 41.º coloquio internacional, ICALP 2014. págs. 39–51. doi :10.1007/978-3-662-43948-7_4.
  19. ^ Lokshtanov, Daniel; Marx, Daniel; Saurabh, Saket (2011). "Límites inferiores basados ​​en la hipótesis del tiempo exponencial". Boletín de la EATCS . 105 : 41–72.
  20. ^ Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional: un enfoque moderno. Cambridge University Press. págs. 362–363. ISBN 9780521424264..
  21. ^ Feige, Uriel (2002). "Relaciones entre la complejidad de caso promedio y la complejidad de aproximación". Actas del 34.º Simposio Anual de la ACM sobre Teoría de la Computación (STOC) . págs. 534–543. doi :10.1145/509907.509985.
  22. ^ Berthet, Quentin; Rigollet, Philippe (2013). "Límites inferiores teóricos de complejidad para la detección de componentes principales dispersos". COLT 2013. págs. 1046–1066.
  23. ^ Hazan, Elad; Krauthgamer, Robert (2011). "¿Qué tan difícil es aproximarse al mejor equilibrio de Nash?". SIAM Journal on Computing . 40 (1): 79–91. CiteSeerX 10.1.1.139.7326 . doi :10.1137/090766991. 
  24. ^ Raghavendra, Prasad (2008). "¿Algoritmos óptimos y resultados de inaproximabilidad para cada CSP?". 40.º Simposio anual de la ACM sobre teoría de la computación (STOC) 2008. págs. 245–254. doi :10.1145/1374376.1374414.
  25. ^ Raghavendra, Prasad; Steurer, David (2010). "Expansión de grafos y la conjetura de juegos únicos". 42.º Simposio anual de la ACM sobre teoría de la computación (STOC) 2010. págs. 755–764. doi :10.1145/1806689.1806792.
  26. ^ Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014). "Inaproximabilidad del ancho de árbol y problemas relacionados". Revista de investigación en inteligencia artificial . 49 : 569–600. doi : 10.1613/jair.4030 .
  27. ^ Vassilevska Williams, Virginia (2018). "Sobre algunas cuestiones de grano fino en algoritmos y complejidad". ICM 2018 (PDF) .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Computational_hardness_assumption&oldid=1190980511"