Hispanopedia Wiki
Articulo de referencia

Suposición de dificultad computacional

En la teoría de la complejidad computacional , una suposición de dificultad computacional es la hipótesis de que un problema particular no puede resolverse de manera eficiente (...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de la complejidad computacional , una suposición de dificultad computacional es la hipótesis de que un problema particular no puede resolverse de manera eficiente (donde eficiente generalmente significa "en tiempo polinomial "). No se sabe cómo demostrar la dificultad (incondicional) para prácticamente cualquier problema útil. En cambio, los informáticos recurren a reducciones para relacionar formalmente la dificultad de un problema nuevo o complejo con una suposición de dificultad computacional sobre un problema mejor comprendido.

En criptografía, las suposiciones sobre la dificultad computacional son de particular importancia . Un objetivo fundamental en criptografía es crear primitivas criptográficas con seguridad demostrable . En algunos casos, se ha comprobado que los protocolos criptográficos poseen seguridad desde el punto de vista de la teoría de la información ; el cifrado de un solo uso es un ejemplo común. Sin embargo, no siempre se puede lograr la seguridad desde el punto de vista de la teoría de la información; 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 tenga limitaciones computacionales , como ocurre en la práctica con todos los adversarios.

Las suposiciones de dificultad 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 dificultad computacional bien estudiada como P ≠ NP .

Comparación de supuestos de dureza

Los informáticos tienen diferentes maneras de evaluar qué supuestos de complejidad son más fiables.

Supuestos de dureza de la resistencia

Decimos que esa suposiciónA{\displaystyle A}es más fuerte que la suposiciónB{\displaystyle B}cuandoA{\displaystyle A}implicaB{\displaystyle B}(y lo contrario es falso o desconocido). En otras palabras, incluso si se asumeA{\displaystyle A}eran falsos, suposiciónB{\displaystyle B}Puede que aún sea cierto, y los protocolos criptográficos basados ​​en suposicionesB{\displaystyle B}Aún podría ser seguro utilizarlo. Por lo tanto, al diseñar protocolos criptográficos, se espera poder demostrar la seguridad utilizando las suposiciones más débiles posibles.

Supuestos del caso promedio frente a supuestos del peor caso

Una suposición de caso promedio indica 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 indica que el problema es difícil en algunas instancias. Para un problema dado, la dificultad en el caso promedio implica la dificultad en el peor caso, por lo que una suposición de dificultad en el caso promedio es más fuerte que una suposición de dificultad en el 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 caso) 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 (incluyendo RSA , logaritmo discreto y algunos problemas de retículos ) pueden basarse en suposiciones de peor caso mediante reducciones de peor caso a caso promedio. [ 3 ]

Falsabilidad

Una característica deseada de una suposición de dificultad computacional es la falsabilidad , es decir, que si la suposición fuera falsa, sería posible probarla. En particular, Naor (2003) introdujo una noción formal de falsabilidad criptográfica. [ 4 ] En términos generales, se dice que una suposición de dificultad 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 la suposición es falsa.

Supuestos comunes de dificultad criptográfica

Existen numerosas suposiciones sobre la robustez criptográfica. Esta es una lista de algunas de las más comunes, junto con algunos protocolos criptográficos que las utilizan.

Factorización de enteros

Dado un número entero compuestonorte{\displaystyle n}y en particular uno que sea el producto de dos primos grandesnorte=pag⋅q{\displaystyle n=p\cdot q}, el problema de factorización de enteros consiste en encontrarpag{\displaystyle p}yq{\displaystyle q}(más generalmente, encontrar números primos)pag1,…,pagk{\displaystyle p_{1},\dots ,p_{k}}de tal manera quenorte=∏ipagi{\displaystyle n=\prod _{i}p_{i}}). 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 la representación (registro⁡norte{\displaystyle \log n}La seguridad de muchos protocolos criptográficos se basa en la suposición de que la factorización de enteros es difícil (es decir, no se puede resolver en tiempo polinomial). Entre los criptosistemas cuya seguridad es equivalente a esta suposición se incluyen la firma de Rabin y el criptosistema de Okamoto-Uchiyama . Muchos otros criptosistemas se basan en suposiciones más fuertes, como RSA , problemas de residuos y ocultación de phi .

Problema RSA

Dado un número compuestonorte{\displaystyle n}, exponentemi{\displaystyle e}y númerodo:=metromi(metroodnorte){\displaystyle c:=m^{e}(\mathrm {mod} \;n)}, el problema RSA consiste en encontrarmetro{\displaystyle m}Se supone que el problema es difícil, pero se vuelve fácil dada la factorización denorte{\displaystyle n}. En el criptosistema RSA ,(norte,mi){\displaystyle (n,e)}es la clave pública ,do{\displaystyle c}es el cifrado del mensajemetro{\displaystyle m}y la factorización denorte{\displaystyle n}es la clave secreta utilizada para el descifrado.

Problemas de residuos

Dado un número compuestonorte{\displaystyle n}y números enterosy,d{\displaystyle y,d}, el problema de la resiliencia consiste en determinar si existe (alternativamente, encontrar un)incógnita{\displaystyle x}de tal manera que

incógnitad≡y(modnorte).{\displaystyle x^{d}\equiv y{\pmod {n}}.}

Entre los casos especiales importantes se incluyen el problema de la resiliencia cuadrática y el problema de la resiliencia compuesta decisional . Al igual que en el caso de RSA, se conjetura que este problema (y sus casos especiales) son difíciles, pero se vuelven fáciles dada la factorización denorte{\displaystyle n}Algunos criptosistemas que se basan en la dificultad de los problemas de residuo incluyen:

Suposición de ocultamiento de Phi

Para un número compuestometro{\displaystyle m}No se sabe cómo calcular eficientemente su función totiente de Euler.ϕ(metro){\displaystyle \phi (m)}La suposición de ocultación de phi postula que es difícil calcularϕ(metro){\displaystyle \phi (m)}y además incluso calcular cualquier factor primo deϕ(metro){\displaystyle \phi (m)}es difícil. Esta suposición se utiliza en el protocolo PIR de Cachin-Micali-Stadler . [ 5 ]

Problema de logaritmo discreto (DLP)

Elementos dadosa{\displaystyle a}yb{\displaystyle b}de un grupoGRAMO{\displaystyle G}El problema del logaritmo discreto pide un número entero.k{\displaystyle k}de tal manera quea=bk{\displaystyle a=b^{k}}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 .

La mayoría de los protocolos criptográficos relacionados con el problema del logaritmo discreto en realidad se basan en la suposición más fuerte de Diffie-Hellman : dados los elementos del grupogramo,gramoa,gramob{\displaystyle g,g^{a},g^{b}}, dóndegramo{\displaystyle g}es un generador ya,b{\displaystyle a,b}son enteros aleatorios, es difícil encontrarlosgramoa⋅b{\displaystyle g^{a\cdot b}}Entre los ejemplos de protocolos que utilizan esta suposición se incluyen el intercambio de claves Diffie-Hellman original , así como el cifrado ElGamal (que se basa en la variante Decisional Diffie-Hellman (DDH), aún más robusta).

mapas multilineales

Un mapa multilineal es una funciónmi:GRAMO1,…,GRAMOnorte→GRAMOT{\displaystyle e:G_{1},\dots ,G_{n}\rightarrow G_{T}}(dóndeGRAMO1,…,GRAMOnorte,GRAMOT{\displaystyle G_{1},\dots ,G_{n},G_{T}}son grupos ) tales que para cualquiergramo1,…,gramonorte∈GRAMO1,…GRAMOnorte{\displaystyle g_{1},\dots ,g_{n}\in G_{1},\dots G_{n}}ya1,…,anorte{\displaystyle a_{1},\dots ,a_{n}},

mi(gramo1a1,…,gramonorteanorte)=mi(gramo1,…,gramonorte)a1⋯anorte{\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 querría construir gruposGRAMO1,…,GRAMOnorte,GRAMOT{\displaystyle G_{1},\dots ,G_{n},G_{T}}y un mapami{\displaystyle e}de tal manera que el mapa y las operaciones del grupo enGRAMO1,…,GRAMOnorte,GRAMOT{\displaystyle G_{1},\dots ,G_{n},G_{T}}se puede calcular de manera eficiente, pero el problema del logaritmo discreto enGRAMO1,…,GRAMOnorte{\displaystyle G_{1},\dots ,G_{n}}sigue siendo difícil. [ 6 ] Algunas aplicaciones requieren supuestos más fuertes, por ejemplo, análogos multilineales de los supuestos de Diffie-Hellman.

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

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

Problemas de retículos

El problema computacional más fundamental en retículos es el problema del vector más corto (SVP) : dado un retículoL{\displaystyle L}, encuentra el vector no nulo más cortov∈L{\displaystyle v\in L}La mayoría de los criptosistemas requieren supuestos más fuertes sobre variantes de SVP, como el problema de vectores independientes más cortos (SIVP) , GapSVP , [ 10 ] o Unique-SVP. [ 11 ]

La suposición de dureza reticular más útil en criptografía es para el problema de aprendizaje con errores (LWE): Dados los ejemplos a(incógnita,y){\displaystyle (x,y)}, dóndey=F(incógnita){\displaystyle y=f(x)}para alguna función linealF(⋅){\displaystyle f(\cdot )}Es fácil de aprenderF(⋅){\displaystyle f(\cdot )}utilizando álgebra lineal . En el problema LWE, la entrada al algoritmo tiene errores, es decir, para cada pary≠F(incógnita){\displaystyle y\neq f(x)}con una pequeña probabilidad . Se cree que los errores hacen que el problema sea intratable (para parámetros apropiados); en particular, se conocen reducciones del peor caso al caso promedio a partir de variantes de SVP. [ 12 ]

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

Algunos criptosistemas que se basan en la dificultad de los problemas de retículos incluyen:

Supuestos de resistencia no criptográfica

Además de sus aplicaciones criptográficas, las suposiciones de dificultad 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 la suposición de dificultad implica algún enunciado deseado de la teoría de la complejidad, en lugar de probar que el enunciado es verdadero en sí mismo. La suposición más conocida de este tipo es la de que P ≠ NP , [ 14 ] pero otras incluyen la hipótesis del tiempo exponencial , [ 15 ] la conjetura de la camarilla plantada y la conjetura de los juegos únicos . [ 16 ]

Problemas difíciles de C

Se sabe que muchos problemas computacionales del peor caso son difíciles o incluso completos para alguna clase de complejidad.do{\displaystyle C}, en particular NP-difíciles (pero a menudo también PSPACE-difíciles , PPAD-difíciles , etc.). Esto significa que son al menos tan difíciles como cualquier problema de la clasedo{\displaystyle C}. Si hay un problemado{\displaystyle C}-difícil (con respecto a las reducciones de tiempo polinomial), entonces no puede resolverse mediante un algoritmo de tiempo polinomial a menos que se cumpla la suposición de dificultad computacional.PAG≠do{\displaystyle P\neq C}es falso.

Hipótesis del tiempo exponencial (HTE) y sus variantes

La hipótesis del tiempo exponencial (ETH) es un fortalecimiento dePAG≠nortePAG{\displaystyle P\neq NP}Suposición de dureza, que conjetura que el problema de satisfacibilidad booleana (SAT) no solo no tiene un algoritmo de tiempo polinomial, sino que además requiere un tiempo exponencial (2Ω(norte){\displaystyle 2^{\Omega (n)}}). [ 17 ] Una suposición aún más fuerte, conocida como la hipótesis del tiempo exponencial fuerte (SETH), conjetura quek{\displaystyle k}-SAT requiere2(1−εk)norte{\displaystyle 2^{(1-\varepsilon _ {k})n}}tiempo, dondelímitek→∞εk=0{\displaystyle \lim _{k\rightarrow \infty }\varepsilon _{k}=0}ETH, SETH y supuestos de dificultad computacional relacionados permiten deducir resultados de complejidad de grano fino, por ejemplo, resultados que distinguen el tiempo polinomial y el tiempo cuasipolinomial , [ 1 ] o inclusonorte1,99{\displaystyle n^{1.99}}versusnorte2{\displaystyle n^{2}}. [ 18 ] Tales supuestos también son útiles en la complejidad parametrizada . [ 19 ]

Suposiciones de dureza 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 grafo aleatorio muestreado, mediante el muestreo de un grafo aleatorio de Erdős-Rényi y luego "plantando" una camarilla aleatoria.k{\displaystyle k}-camarilla, es decir, conectark{\displaystyle k}nodos uniformemente aleatorios (donde2registro2⁡norte≪k≪norte{\displaystyle 2\log _{2}n\ll k\ll {\sqrt {n}}}), y el objetivo es encontrar la plantadak{\displaystyle k}-clique (que es whp único). [ 20 ] Otro ejemplo importante es la hipótesis de Feige , que es una suposición de dificultad computacional sobre instancias aleatorias de 3-SAT (muestreadas para mantener una proporción específica de cláusulas a variables). [ 21 ] Las suposiciones de dificultad computacional del caso promedio son útiles para probar la dificultad del caso promedio en aplicaciones como la estadística, donde hay una distribución natural sobre las entradas. [ 22 ] Además, la suposición de dificultad de clique plantada también se ha utilizado para distinguir entre la complejidad temporal del peor caso polinomial y cuasipolinomial de otros problemas, [ 23 ] de manera similar a la hipótesis del tiempo exponencial .

Juegos únicos

El problema de la cubierta de etiquetas únicas es un problema de satisfacción de restricciones, donde cada restriccióndo{\displaystyle C}implica dos variablesincógnita,y{\displaystyle x,y}y para cada valor deincógnita{\displaystyle x}existe un valor único dey{\displaystyle y}que satisfacedo{\displaystyle C}. Determinar si todas las restricciones pueden ser satisfechas es fácil, pero la conjetura del juego único (UGC) postula que determinar si casi todas las restricciones ((1−ε){\displaystyle (1-\varepsilon )}-fracción, para cualquier constanteε>0{\displaystyle \varepsilon >0}) pueden quedar satisfechos o casi ninguno de ellos (ε{\displaystyle \varepsilon }La condición -fracción) puede satisfacerse, lo cual es NP-difícil. [ 16 ] A menudo se sabe que los problemas de aproximación son NP-difíciles asumiendo UGC; estos problemas se denominan UG-difíciles. En particular, asumiendo UGC, existe un algoritmo de programación semidefinida que logra garantías de aproximación óptimas para muchos problemas importantes. [ 24 ]

Expansión de conjunto pequeño

Estrechamente relacionado con el problema de la cobertura de etiquetas únicas se encuentra el problema de la expansión de conjuntos pequeños (SSE) : Dado un grafoGRAMO=(V,mi){\displaystyle G=(V,E)}, encontrar un pequeño conjunto de vértices (de tamañonorte/registro⁡(norte){\displaystyle n/\log(n)}) cuya expansión de aristas es mínima. Se sabe que si SSE es difícil de aproximar, también lo es la cobertura de etiquetas ú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-difíciles [ 26 ] (es decir, al menos tan difíciles como aproximar SSE).

La conjetura 3SUM

Dado un conjunto denorte{\displaystyle n}El problema 3SUM pregunta si existe una terna 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 un "tiempo verdaderamente subcuadrático": la conjetura 3SUM es la suposición de dificultad computacional de que no existenO(norte2−ε){\displaystyle O(n^{2-\varepsilon })}-algoritmos de tiempo para 3SUM (para cualquier constante)ε>0{\displaystyle \varepsilon >0}). Esta conjetura es útil para demostrar cotas inferiores casi cuadráticas para varios problemas, principalmente de geometría computacional . [ 27 ]

Véase también

Referencias

  1. 1 2 Braverman, Mark ; Ko, Young Kun; Weinstein, Omri (2015). "Aproximación del mejor equilibrio de Nash ennorteo(registro⁡(norte)){\displaystyle n^{o(\log(n))}}El 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  978-1-61197-374-7.
  2. ↑ J. Katz y Y. Lindell, Introducción a la criptografía moderna (Serie de criptografía y seguridad de redes de Chapman and Hall/CRC), Chapman and 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. Lecture Notes in Computer Science. Vol. 9562. Springer. pp. 505–522 . doi : 10.1007/978-3-662-49096-9_21 . ISBN   978-3-662-49095-2.
  4. ↑ Naor, Moni (2003). "Sobre supuestos y desafíos criptográficos". En Boneh, Dan (ed.). Avances en criptología – CRYPTO 2003: 23.ª Conferencia Internacional Anual de Criptología, Santa Bárbara, California, EE. UU., 17-21 de agosto de 2003, Actas . Lecture Notes in Computer Science. Vol. 2729. Berlín: Springer. pp. 96–109 . doi : 10.1007/978-3-540-45146-4_6 . ISBN   978-3-540-40674-7. 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 . Lecture Notes in Computer Science. Vol. 1592. Springer. pp. 402–414 . doi : 10.1007/3-540-48910-X_28 . ISBN   978-3-540-65889-4. S2CID 29690672 . 
  6. ↑ Boneh, Dan ; Silverberg, Alice (2002). "Aplicaciones de formas multilineales a la criptografía" . Cryptology ePrint Archive .
  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. "¿Está roto ya el esquema de codificación graduada?" . 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 candidata y cifrado funcional para todos los circuitos" (PDF) . SIAM Journal on Computing . 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 extendido". 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 entre el peor y el 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 . ISBN  0-89791-888-6.
  12. ↑ Regev, Oded (2010). "El problema del aprendizaje con errores (Encuesta invitada)". Conferencia sobre Complejidad Computacional (CCC) 2010. pp. 191–204 . doi : 10.1109/CCC.2010.26 . ISBN  978-1-4244-7214-7.
  13. ↑ Peikert, Chris (2016). "Una década de criptografía reticular" . 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) . Communications of the ACM . 52 (9): 78–86 . doi : 10.1145/1562164.1562186 . S2CID 5969255. Archivado del original (PDF) el 24 de febrero de 2011. .
  15. ↑ Woeginger, Gerhard (2003). «Algoritmos exactos para problemas NP-difíciles: una revisión». Optimización combinatoria: ¡Eureka, te encoges! Notas de clase en informática. Vol. 2570. Springer-Verlag. págs. 185–207 . doi : 10.1007/3-540-36478-1_17 . ISBN   978-3-540-00580-3. S2CID 289357 . .
  16. 1 2 Khot, Subhash (2010). "Sobre la conjetura de los juegos únicos". Actas de la 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 . ISBN  0-7695-0075-7.
  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. Lecture Notes in Computer Science. Vol. 8572. pp. 39–51 . doi : 10.1007/978-3-662-43948-7_4 . ISBN   978-3-662-43947-0.
  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 del 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 . ISBN  1-58113-495-9.
  22. ↑ Berthet, Quentin; Rigollet, Philippe (2013). "Límites inferiores teóricos de complejidad para la detección de componentes principales dispersas". COLT 2013. págs. 1046–1066 . 
  23. ↑ Hazan, Elad; Krauthgamer, Robert (2011). "¿Qué tan difícil es aproximar el 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 . ISBN  978-1-60558-047-0.
  25. ↑ Raghavendra, Prasad; Steurer, David (2010). «Expansión de grafos y la conjetura de los 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 . ISBN  978-1-4503-0050-6.
  26. ↑ Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014). "Inaproximabilidad del ancho de árbol y problemas relacionados" . Journal of Artificial Intelligence Research . 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) .
Lecturas relacionadas
6 articulos
Teoría de la complejidad computacionalEn la informática teórica y las matemáticas, la teoría de la complejidad computacional se centra en la clasificación de los problemas computacional...Complejidad temporalComplejidad temporalEn informática teórica , la complejidad temporal es la complejidad computacional que describe la cantidad de tiempo que tarda un ordenador en ejecu...Prueba matemáticaPrueba matemáticaP. Oxy. 29 , uno de los fragmentos más antiguos que se conservan de los Elementos de Euclides , un libro de texto utilizado durante milenios para e...Científico informáticoCientífico informáticoUn científico informático es un científico que se especializa en el estudio académico de la informática . [1]Reducción (complejidad)Reducción (complejidad)En la teoría de la computabilidad y la teoría de la complejidad computacional , una reducción es un algoritmo para transformar un problema en otro....Máquina de cifrado de Lorenz de doce rotores con mecanismoCriptografíaMáquina de cifrado de Lorenz , utilizada en la Segunda Guerra Mundial para cifrar las comunicaciones del Alto Mando alemán La criptografía , o crip...