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 normalmente significa "en tiempo polinómico "). No se sabe cómo probar la dureza (incondicional) para prácticamente ningún problema útil. En cambio, los 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 comprende mejor.

Los supuestos de dureza computacional son de particular importancia en criptografía . Un objetivo importante 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é computacionalmente limitado , como lo son todos los adversarios en la práctica.

Los supuestos de dureza computacional también son útiles para guiar a los diseñadores de algoritmos : es poco probable que un algoritmo simple refute un supuesto de dureza computacional bien estudiado, como P ≠ NP .

Comparación de supuestos de dureza

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

Suposiciones de fuerza de dureza.

Decimos que la suposición es más fuerte que la suposición cuando implica (y lo contrario es falso o desconocido). En otras palabras, incluso si la suposición fuera falsa, la suposición aún puede ser cierta y los protocolos criptográficos basados ​​en suposiciones aún pueden ser seguros de usar. Por lo tanto, al diseñar protocolos criptográficos, se espera poder demostrar la seguridad utilizando los supuestos más débiles posibles. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$

Supuestos del caso promedio versus el peor de los casos

Un supuesto del caso promedio dice que un problema específico es difícil en la mayoría de los casos a partir de alguna distribución explícita, mientras que un supuesto del peor de los casos solo dice que el problema es difícil en algunos casos. Para un problema dado, la dureza del caso promedio implica la dureza del peor de los casos, por lo que un supuesto de dureza del caso promedio es más fuerte que un supuesto de dureza del peor de los casos para el mismo problema. Además, incluso para problemas incomparables, un supuesto como la Hipótesis del Tiempo Exponencial a menudo se considera preferible a un supuesto 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 casos promedio utilizadas en criptografía (incluido RSA, registro discreto y algunos problemas de red) pueden basarse en suposiciones del peor de los casos mediante reducciones del peor de los casos al caso promedio. ^[3]

Falsificabilidad

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 falsificable 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 sólo si la suposición es falsa.

Supuestos comunes de dureza criptográfica

Se utilizan muchos supuestos de dureza criptográfica. Esta es una lista de algunos de los más comunes y algunos protocolos criptográficos que los utilizan.

factorización de enteros

Dado un número entero compuesto , y en particular uno que es producto de dos números primos grandes , el problema de factorización de enteros es encontrar y (más generalmente, encontrar números primos tales que ). Es un problema abierto importante encontrar un algoritmo para la factorización de números enteros que se ejecute en tiempo polinómico 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 números enteros es difícil (es decir, no se puede resolver en tiempo polinómico). Los criptosistemas cuya seguridad es equivalente a esta suposición incluyen el criptosistema Rabin y el criptosistema Okamoto-Uchiyama . Muchos más criptosistemas se basan en suposiciones más sólidas, como RSA, problemas de residuosidad y ocultación de Phi. ${\displaystyle n}$ ${\displaystyle n=p\cdot q}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p_{1},\dots ,p_{k}}$ ${\displaystyle n=\prod _{i}p_{i}}$ ${\displaystyle \log n}$

problema RSA

Dado un número compuesto , exponente y número , el problema de RSA es encontrarlo . Se conjetura 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. ${\displaystyle n}$ ${\displaystyle e}$ ${\displaystyle c:=m^{e}(\mathrm {mod} \;n)}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle (n,e)}$ ${\displaystyle c}$ ${\displaystyle m}$ ${\displaystyle n}$

Problemas de residuosidad

Dado un número compuesto y números enteros , el problema de residuosidad es determinar si existe (alternativamente, encontrar uno) tal que ${\displaystyle n}$ ${\displaystyle y,d}$ ${\displaystyle x}$

${\displaystyle x^{d}\equiv y{\pmod {n}}.}$

Casos especiales importantes incluyen el problema de residuosidad cuadrática y el problema de residuosidad compuesta de decisión . Como en el caso de RSA, se conjetura que este problema (y sus casos especiales) es difícil, pero se vuelve fácil dada la factorización de . Algunos criptosistemas que dependen de la dureza de los problemas de residualusidad incluyen: ${\displaystyle n}$

• Criptosistema Goldwasser-Micali (problema de residuosidad cuadrática)
• Generador Blum Blum Shub (problema de residuosidad cuadrática)
• Criptosistema Paillier (problema de residuosidad compuesta decisional)
• Criptosistema Benaloh (problema de mayor residuosidad)
• Criptosistema Naccache-Stern (problema de mayor residuosidad)

Suposición de ocultación de phi

Para un número compuesto , no se sabe cómo calcular eficientemente su función totiente de Euler . El supuesto de ocultación de Phi postula que es difícil de calcular y, además, incluso calcular los factores primos de es difícil. Esta suposición se utiliza en el protocolo PIR Cachin-Micali-Stadler . ^[5] ${\displaystyle m}$ ${\displaystyle \phi (m)}$ ${\displaystyle \phi (m)}$ ${\displaystyle \phi (m)}$

Problema de registro discreto (DLP)

Dados elementos y de un grupo , el problema de registros discretos solicita un número entero tal que . No se sabe que el problema del registro discreto sea comparable a la factorización de números enteros, pero sus complejidades computacionales están estrechamente relacionadas . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle a=b^{k}}$

La mayoría de los protocolos criptográficos relacionados con el problema del registro discreto en realidad se basan en la suposición más sólida de Diffie-Hellman : dados los elementos del grupo , donde hay un generador y son números enteros aleatorios, es difícil de encontrar . Ejemplos de protocolos que utilizan esta suposición 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 potente ). ${\displaystyle g,g^{a},g^{b}}$ ${\displaystyle g}$ ${\displaystyle a,b}$ ${\displaystyle g^{a\cdot b}}$

Mapas multilineales

Un mapa multilineal es una función (donde hay grupos ) tal que para cualquiera y , ${\displaystyle e:G_{1},\dots ,G_{n}\rightarrow G_{T}}$ ${\displaystyle G_{1},\dots ,G_{n},G_{T}}$ ${\displaystyle g_{1},\dots ,g_{n}\in G_{1},\dots G_{n}}$ ${\displaystyle a_{1},\dots ,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, a uno le gustaría construir grupos y un mapa de modo que el mapa y las operaciones del grupo se puedan calcular de manera eficiente, pero el problema del registro discreto aún es difícil. ^[6] Algunas aplicaciones requieren supuestos más sólidos, por ejemplo, análogos multilineales de los supuestos de Diffie-Hellman. ${\displaystyle G_{1},\dots ,G_{n},G_{T}}$ ${\displaystyle e}$ ${\displaystyle G_{1},\dots ,G_{n},G_{T}}$ ${\displaystyle G_{1},\dots ,G_{n}}$

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

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

• Esquema Boneh-Franklin (bilineal Diffie-Hellman)
• Boneh – Lynn – Shacham (bilineal Diffie-Hellman)
• Candidato de Garg-Gentry-Halevi-Raykova-Sahai-Waters para la ofuscación de indistinguibilidad y el cifrado funcional (rompecabezas multilineales) ^[9]

Problemas de celosía

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

El supuesto de dureza de la 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 de 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 los parámetros apropiados); en particular, se conocen reducciones del peor de los casos al promedio de las variantes de SVP. ^[12] ${\displaystyle (x,y)}$ ${\displaystyle y=f(x)}$ ${\displaystyle f(\cdot )}$ ${\displaystyle f(\cdot )}$ ${\displaystyle y\neq f(x)}$

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

Algunos criptosistemas que dependen de problemas de dureza de la red incluyen:

• NTRU (tanto NTRUEncrypt como NTRUSign )
• La mayoría de los candidatos para el cifrado totalmente homomórfico

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 afirmaciones matemáticas que son difíciles de probar incondicionalmente. En estas aplicaciones, se demuestra que el supuesto de dureza implica alguna afirmación teórica de la complejidad deseada, en lugar de demostrar que la afirmación es verdadera en sí misma. 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 . ^[dieciséis]

C -problemas difíciles

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

Hipótesis del tiempo exponencial (ETH) y variantes

La Hipótesis del Tiempo Exponencial (ETH) es un fortalecimiento del supuesto de dureza, que conjetura que el problema de satisfacibilidad booleano (SAT) no sólo no tiene un algoritmo de tiempo polinómico, sino que además requiere un tiempo exponencial ( ). ^[17] Una suposición aún más fuerte, conocida como la Hipótesis del Tiempo Exponencial Fuerte (SETH), conjetura de que -SAT requiere tiempo, donde . ETH, SETH y los supuestos de dureza computacional relacionados permiten deducir resultados de complejidad detallados, por ejemplo, resultados que distinguen el tiempo polinomial y el tiempo cuasipolinomial , ^[1] o incluso versus . ^[18] Tales suposiciones también son útiles en complejidad parametrizada . ^[19] ${\displaystyle P\neq NP}$ ${\displaystyle 2^{\Omega (n)}}$ ${\displaystyle k}$ ${\displaystyle 2^{(1-\varepsilon _{k})n}}$ ${\displaystyle \lim _{k\rightarrow \infty }\varepsilon _{k}=0}$ ${\displaystyle n^{1.99}}$ ${\displaystyle n^{2}}$

Supuestos de dureza promedio

Se supone que algunos problemas computacionales son difíciles en promedio en 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 camarilla aleatoria, es decir, conectando nodos uniformemente aleatorios (donde ), y el objetivo es encontrar la camarilla plantada (que es única whp). ^[20] Otro ejemplo importante es la Hipótesis de Feige , que es un supuesto de dureza computacional sobre instancias aleatorias de 3-SAT (muestreadas para mantener una proporción específica de cláusulas y variables). ^[21] Los supuestos de dureza computacional de caso promedio son útiles para probar la dureza de caso promedio en aplicaciones como estadísticas, donde existe una distribución natural sobre las entradas. ^[22] Además, el supuesto de dureza de la camarilla plantada también se ha utilizado para distinguir entre la complejidad temporal del peor de los casos polinómica y cuasipolinomial de otros problemas, ^[23] de manera similar a la hipótesis del tiempo exponencial. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2\log _{2}n\ll k\ll {\sqrt {n}}}$ ${\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 todas las restricciones pueden satisfacerse es fácil, pero la Conjetura Única del Juego (CGU) postula que determinar si casi todas las restricciones ( -fracción, para cualquier constante ) pueden satisfacerse o casi ninguna de ellas ( -fracción) puede satisfacerse. es NP-duro. ^[16] A menudo se sabe que los problemas de aproximación son UGC de NP-difícil suposición; Estos problemas se denominan UG-difíciles. En particular, suponiendo UGC existe un algoritmo de programación semidefinido que logra garantías de aproximación óptimas para muchos problemas importantes. ^[24] ${\displaystyle C}$ ${\displaystyle x,y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle C}$ ${\displaystyle (1-\varepsilon )}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon }$

Expansión de conjunto pequeño

Estrechamente relacionado con el problema de la cubierta de etiqueta única está el problema de expansión de conjuntos pequeños (SSE) : dado un gráfico , encuentre un pequeño conjunto de vértices (de tamaño ) cuya expansión de aristas sea mínima. Se sabe que si el SSE es difícil de aproximar, también lo es la cubierta de etiqueta única. Por lo tanto, la Hipótesis de la Expansión de Conjuntos Pequeños , que postula que la ESS es difícil de aproximar, es una suposición más sólida (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 la aproximación SSE). ${\displaystyle G=(V,E)}$ ${\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 es 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 de 3SUM es la suposición de dureza computacional de que no existen algoritmos de tiempo para 3SUM (para cualquier constante ). Esta conjetura es útil para demostrar límites inferiores casi cuadráticos para varios problemas, principalmente de geometría computacional . ^[27] ${\displaystyle n}$ ${\displaystyle O(n^{2-\varepsilon })}$ ${\displaystyle \varepsilon >0}$

Ver también

• Nivel de seguridad

Referencias

1. Braverman, Mark ; Ko, joven Kun; Weinstein, Omri (2015). "Aproximar el mejor equilibrio de Nash en el tiempo rompe la hipótesis del tiempo exponencial". Simposio sobre Algoritmos Discretos (SODA) . Sociedad de Matemática Industrial y Aplicada . págs. 970–982. doi :10.1137/1.9781611973730.66. ISBN ${\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 seguridad de red y criptografía de 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 de Teoría de la Criptografía (TCC) 2016 . Saltador. págs. 505–522. 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 de Criptología, Santa Bárbara, California, EE. UU., 17 al 21 de agosto de 2003, Actas . Apuntes de conferencias sobre informática. vol. 2729. Berlín: Springer. págs. 96-109. doi : 10.1007/978-3-540-45146-4_6 . SEÑOR  2093188.
5. Cachin, cristiano; Micali, Silvio; Stadler, Markus (1999). "Recuperación de información computacionalmente privada con comunicación polilogarítmica". En Stern, Jacques (ed.). Avances en criptología: EUROCRYPT '99 . Apuntes de conferencias sobre informática. vol. 1592. Saltador. págs. 402–414. doi :10.1007/3-540-48910-X_28. ISBN 978-3-540-65889-4. S2CID  29690672.
6. Boneh, Dan ; Silverberg, Alicia (2002). "Aplicaciones de formas multilineales a la criptografía". Archivo ePrint 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 no funciona el esquema de codificación graduada?" . Consultado el 22 de marzo de 2018 .
9. Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Aguas, Brent (2016). "Ofuscación de indistinguibilidad de candidatos y cifrado funcional para todos los circuitos" (PDF) . Revista SIAM de Computación . 45 (3). SIAM: 882–929. doi :10.1137/14095772X.
10. Peikert, Chris (2009). "Criptosistemas de clave pública del problema del vector más corto en el peor de los casos: resumen ampliado". Actas del 41º Simposio Anual 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 en el peor de los casos/caso promedio". Actas del 29º Simposio Anual de 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 invitada)". Jornada 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 reticular". Fundamentos y Tendencias en Informática Teórica . 10 (4): 283–424. doi :10.1561/0400000074.
14. Por ahora, 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-difíciles: 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. 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". Proc. 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 ; Barac, Booz (2009). Complejidad computacional: un enfoque moderno. Prensa de la Universidad de Cambridge. págs. 362–363. ISBN 9780521424264..
21. Feige, Uriel (2002). "Relaciones entre complejidad media de casos y complejidad de aproximación". Actas del 34º Simposio Anual ACM sobre Teoría de la Computación (STOC) . págs. 534–543. doi :10.1145/509907.509985.
22. Berthet, Quintín; Rigollet, Philippe (2013). "Límites inferiores teóricos de complejidad para la detección de componentes principales dispersos". COLT 2013. págs.
23. Hazán, Elad; Krauthgamer, Robert (2011). "¿Qué tan difícil es aproximarse al mejor equilibrio de Nash?". Revista SIAM de Computación . 40 (1): 79–91. CiteSeerX 10.1.1.139.7326 . doi :10.1137/090766991. 
24. Raghavendra, Prasad (2008). "¿Algoritmos óptimos y resultados de inaccesibilidad para cada CSP?". 40º Simposio Anual 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 gráficos y conjetura de juegos únicos". 42º Simposio Anual ACM sobre teoría de la Computación (STOC) 2010 . págs. 755–764. doi :10.1145/1806689.1806792.
26. Wu, Yu; Austrian, Per; Pitassi, Toniann; Liu, David (2014). "Inaproximabilidad del ancho de los árboles 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 detalladas sobre algoritmos y complejidad". ICI 2018 (PDF) .