Complejidad del caso promedio

En la teoría de la complejidad computacional , la complejidad promedio de un algoritmo es la cantidad de algún recurso computacional (generalmente tiempo) que utiliza, promediada sobre todas las posibles entradas. Se suele contrastar con la complejidad del peor caso , que considera la complejidad máxima del algoritmo sobre todas las posibles entradas.

Hay tres motivaciones principales para estudiar la complejidad del caso promedio. ^{[ 1 ]} Primero, aunque algunos problemas pueden ser intratables en el peor caso, las entradas que provocan este comportamiento pueden ocurrir raramente en la práctica, por lo que la complejidad del caso promedio puede ser una medida más precisa del rendimiento de un algoritmo. Segundo, el análisis de la complejidad del caso promedio proporciona herramientas y técnicas para generar instancias difíciles de problemas que pueden utilizarse en áreas como la criptografía y la desaleatorización . Tercero, la complejidad del caso promedio permite discriminar el algoritmo más eficiente en la práctica entre algoritmos de complejidad equivalente en el mejor caso (por ejemplo, Quicksort ).

El análisis del caso promedio requiere la noción de una entrada "promedio" para un algoritmo, lo que lleva al problema de diseñar una distribución de probabilidad sobre las entradas. Alternativamente, se puede utilizar un algoritmo aleatorio . El análisis de dichos algoritmos conduce a la noción relacionada de complejidad esperada . ^{[ 2 ]}^{: 28}

Historia y antecedentes

El rendimiento promedio de los algoritmos se ha estudiado desde que se desarrollaron las nociones modernas de eficiencia computacional en la década de 1950. Gran parte de este trabajo inicial se centró en problemas para los que ya se conocían algoritmos de tiempo polinomial en el peor de los casos. ^{[ 3 ]} En 1973, Donald Knuth ^{[ 4 ]} publicó el Volumen 3 de El arte de la programación de computadoras, que analiza exhaustivamente el rendimiento promedio de los algoritmos para problemas resolubles en tiempo polinomial en el peor de los casos, como la ordenación y la búsqueda de la mediana.

Un algoritmo eficiente para problemas $NP$ -completos se caracteriza generalmente por ejecutarse en tiempo polinomial para todas las entradas; esto equivale a exigir una complejidad eficiente en el peor de los casos. Sin embargo, un algoritmo que resulta ineficiente con un número reducido de entradas puede ser eficiente para la mayoría de las entradas que se presentan en la práctica. Por lo tanto, es conveniente estudiar las propiedades de estos algoritmos, donde la complejidad en el caso promedio puede diferir de la complejidad en el peor de los casos, y encontrar métodos para relacionar ambas.

Las nociones fundamentales de complejidad del caso promedio fueron desarrolladas por Leonid Levin en 1986 cuando publicó un documento de una página ^{[ 5 ]} definiendo la complejidad del caso promedio y la completitud mientras daba un ejemplo de un problema completo para $distNP$ , el análogo del caso promedio de $NP$ .

Definiciones

Complejidad eficiente en el caso promedio

La primera tarea es definir con precisión qué se entiende por un algoritmo que es eficiente "en promedio". Un intento inicial podría definir un algoritmo eficiente en el caso promedio como aquel que se ejecuta en tiempo polinomial esperado sobre todas las entradas posibles. Esta definición tiene varias deficiencias; en particular, no es robusta a cambios en el modelo computacional. Por ejemplo, supongamos que el algoritmo $A$ se ejecuta en tiempo $t A (x)$ en la entrada $x$ y el algoritmo $B$ se ejecuta en tiempo $t A (x) 2$ en la entrada $x$ ; es decir, $B$ es cuadráticamente más lento que $A$ . Intuitivamente, cualquier definición de eficiencia en el caso promedio debería capturar la idea de que $A$ es eficiente en promedio si y solo si $B$ es eficiente en promedio. Supongamos, sin embargo, que las entradas se extraen aleatoriamente de la distribución uniforme de cadenas con longitud $n$ , y que $A$ se ejecuta en tiempo $n 2$ en todas las entradas excepto la cadena $1 n$ para la cual $A$ toma tiempo $2 n$ . Entonces se puede comprobar fácilmente que el tiempo de ejecución esperado de $A$ es polinomial, pero el tiempo de ejecución esperado de $B$ es exponencial. ^{[ 3 ]}

Para crear una definición más sólida de eficiencia en el caso promedio, tiene sentido permitir que un algoritmo $A$ se ejecute durante más tiempo que un tiempo polinomial en algunas entradas, pero la fracción de entradas en las que $A requiere un tiempo de ejecución cada vez mayor se reduce progresivamente. Esta intuición se refleja en la siguiente fórmula para el tiempo de ejecución polinomial promedio, que equilibra la$ relación de compromiso polinomial entre el tiempo de ejecución y la fracción de entradas:

\Pr _{x\in _{R}D_{n}}\left[t_{A}(x)\geq t\right]\leq {\frac {p(n)}{t^{\epsilon }}}

for every $n, t > 0$ and polynomial $p$ , where $t A (x)$ denotes the running time of algorithm $A$ on input $x$ , and $ε$ is a positive constant value.^[6] Alternatively, this can be written as

E_{x\in _{R}D_{n}}\left[{\frac {t_{A}(x)^{\epsilon }}{n}}\right]\leq C

for some constants $C$ and $ε$ , where $n = | x |$ .^[7] In other words, an algorithm $A$ has good average-case complexity if, after running for $t A (n)$ steps, $A$ can solve all but a $⁠ n c / (t A (n)) ε ⁠$ fraction of inputs of length $n$ , for some $ε, c > 0$ .^[3]

Distributional problem

The next step is to define the "average" input to a particular problem. This is achieved by associating the inputs of each problem with a particular probability distribution. That is, an "average-case" problem consists of a language $L$ and an associated probability distribution $D$ which forms the pair $(L, D)$ .^[7] The two most common classes of distributions which are allowed are:

Polynomial-time computable distributions ( $P$ -computable): these are distributions for which it is possible to compute the cumulative density of any given input $x$ . More formally, given a probability distribution $μ$ and a string $x \in {0, 1} n$ it is possible to compute the value $\mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]$ in polynomial time. This implies that $Pr[x]$ is also computable in polynomial time.
Polynomial-time samplable distributions ( $P$ -samplable): these are distributions from which it is possible to draw random samples in polynomial time.

These two formulations, while similar, are not equivalent. If a distribution is $P$ -computable it is also $P$ -samplable, but the converse is not true if $P$ ≠ $P #P$ .^[7]

AvgP and distNP

Un problema de distribución $(L, D)$ pertenece a la clase de complejidad $AvgP$ si existe un algoritmo eficiente para el caso promedio de $L$ , tal como se definió anteriormente. En la literatura, la clase $AvgP$ se denomina ocasionalmente $distP .$ ^{[ 7 ]}

Un problema distribucional $(L, D)$ pertenece a la clase de complejidad $distNP$ si $L$ está en $NP$ y $D$ es $P$ -computable. Cuando $L$ está en $NP$ y $D$ es $P$ -muestreable, $(L, D)$ pertenece a $sampNP$ . ^{[ 7 ]}

En conjunto, $AvgP$ y $distNP$ definen los análogos del caso promedio de $P$ y $NP$ , respectivamente. ^{[ 7 ]}

Reducciones entre problemas de distribución

Sean $(L, D)$ y $(L', D')$ dos problemas de distribución. El caso promedio $de (L, D) se reduce a$ $(L', D')$ (escrito $(L, D) \leq AvgP (L', D')$ ) si existe una función $f$ que para cada $n$ , en la entrada $x$ se puede calcular en tiempo polinomial en $n$ y

(Corrección) $x \in L$ si y solo si $f (x) \in L'$
(Dominación ) Existen polinomios $p$ y $m$ tales que, para todo $n$ e y $,$ $\sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)$

La condición de dominación impone la noción de que si el problema $(L, D)$ es difícil en promedio, entonces $(L', D')$ también lo es en promedio. Intuitivamente, una reducción debería proporcionar una forma de resolver una instancia $x$ del problema $L$ calculando $f (x)$ y alimentando el resultado al algoritmo que resuelve $L'$ . Sin la condición de dominación, esto podría no ser posible, ya que el algoritmo que resuelve $L$ en tiempo polinomial en promedio podría tomar tiempo superpolinomial en un número pequeño de entradas, pero $f$ podría mapear estas entradas a un conjunto mucho mayor de $D',$ de modo que el algoritmo $A'$ ya no se ejecute en tiempo polinomial en promedio. La condición de dominación solo permite que tales cadenas aparezcan polinomialmente como frecuencia en $D'$ . ^{[ 6 ]}

Problemas DistNP-completos

El análogo en el caso promedio de $la NP$ -completitud es $la distNP$ -completitud. Un problema distribucional $(L', D')$ es $distNP$ -completo si $(L', D')$ está en $distNP$ y para cada $(L, D)$ en $distNP$ , $(L, D)$ es reducible en el caso promedio a $(L', D')$ . ^{[ 7 ]}

Un ejemplo de un problema $distNP$ -completo es el Problema de la Parada Acotada , $(BH, D)$ (para cualquier D $P$ -computable ) definido de la siguiente manera:

$BH=\{(M,x,1^{t}):M{\text{ es una máquina de Turing no determinista que acepta }}x{\text{ en}}\leq t{\text{ pasos}}\}$ ^{[ 7 ]}

En su artículo original, Levin mostró un ejemplo de un problema de teselado distribucional que es $NP$ -completo en el caso promedio. ^{[ 5 ]} Un estudio de los problemas NP-completos $dist$ conocidos está disponible en línea. ^{[ 6 ]}

Un área de investigación activa consiste en encontrar nuevos problemas $distNP$ -completos. Sin embargo, encontrar tales problemas puede ser complicado debido a un resultado de Gurevich que muestra que cualquier problema distribucional con una distribución plana no puede ser $distNP$ -completo a menos que $EXP$ = $NEXP$ . ^{[ 8 ]} (Una distribución plana $μ$ es aquella para la cual existe un $ε > 0$ tal que para cualquier $x$ , $μ (x) \leq 2 - | x | ε$ $.) Un resultado de Livne muestra que todos los problemas NP$ -completos naturales tienen versiones $DistNP$ -completas. ^{[ 9 ]} Sin embargo, el objetivo de encontrar un problema distribucional natural que sea $DistNP$ -completo aún no se ha logrado. ^{[ 10 ]}

Aplicaciones

Algoritmos de ordenación

Como se mencionó anteriormente, gran parte del trabajo inicial relacionado con la complejidad promedio se centró en problemas para los cuales ya existían algoritmos de tiempo polinomial, como la ordenación. Por ejemplo, muchos algoritmos de ordenación que utilizan aleatoriedad, como $Quicksort$ , tienen un tiempo de ejecución en el peor de los casos de $O(n²)$ , pero un tiempo de ejecución promedio de $O(n log(n))$ , donde $n$ es la longitud de la entrada a ordenar. ^{[ 2 ]}

Criptografía

Para la mayoría de los problemas, se realiza un análisis de complejidad en el caso promedio para encontrar algoritmos eficientes para un problema que se considera difícil en el peor de los casos. Sin embargo, en las aplicaciones criptográficas, ocurre lo contrario: la complejidad en el peor de los casos es irrelevante; en cambio, queremos garantizar que la complejidad en el caso promedio de todo algoritmo que "rompe" el esquema criptográfico sea ineficiente. ^{[ 11 ]}

Por lo tanto, todos los esquemas criptográficos seguros se basan en la existencia de funciones unidireccionales . ^{[ 3 ]} Aunque la existencia de funciones unidireccionales sigue siendo un problema abierto , muchas funciones unidireccionales candidatas se basan en problemas difíciles como la factorización de enteros o el cálculo del logaritmo discreto . Nótese que no es deseable que la función candidata sea $NP$ -completa, ya que esto solo garantizaría que probablemente no exista un algoritmo eficiente para resolver el problema en el peor de los casos; lo que realmente queremos es una garantía de que ningún algoritmo eficiente pueda resolver el problema sobre entradas aleatorias (es decir, el caso promedio). De hecho, tanto el problema de la factorización de enteros como el del logaritmo discreto están en $NP \cap$ $coNP$ y, por lo tanto, no se consideran $NP$ -completos. ^{[ 7 ]} El hecho de que toda la criptografía se predique en la existencia de problemas intratables en el caso promedio en $NP$ es una de las principales motivaciones para estudiar la complejidad del caso promedio.

Otros resultados

El principio de Yao , de un artículo de Andrew Yao de 1978 , muestra que para amplias clases de problemas computacionales, la complejidad promedio para una distribución de entrada difícil y un algoritmo determinista adaptado a esa distribución es la misma que la complejidad esperada para un algoritmo aleatorio rápido y su entrada en el peor de los casos. ^{[ 12 ]}

En 1990, Impagliazzo y Levin demostraron que si existe un algoritmo eficiente de caso promedio para un problema $distNP$ -completo bajo la distribución uniforme, entonces existe un algoritmo de caso promedio para cada problema en $NP$ bajo cualquier distribución muestreable en tiempo polinomial. ^{[ 13 ]} Aplicar esta teoría a problemas distribucionales naturales sigue siendo una cuestión abierta pendiente. ^{[ 3 ]}

En 1992, Ben-David et al. demostraron que si todos los lenguajes en $distNP$ tienen algoritmos de decisión buenos en promedio, también tienen algoritmos de búsqueda buenos en promedio. Además, demostraron que esta conclusión se mantiene bajo una suposición más débil: si cada lenguaje en $NP$ es fácil en promedio para los algoritmos de decisión con respecto a la distribución uniforme, entonces también es fácil en promedio para los algoritmos de búsqueda con respecto a la distribución uniforme. ^{[ 14 ]} Por lo tanto, las funciones criptográficas unidireccionales solo pueden existir si hay problemas $distNP$ sobre la distribución uniforme que son difíciles en promedio para los algoritmos de decisión.

En 1993, Feigenbaum y Fortnow demostraron que no es posible probar, bajo reducciones aleatorias no adaptativas, que la existencia de un algoritmo bueno en promedio para un problema $distNP$ -completo bajo la distribución uniforme implique la existencia de algoritmos eficientes en el peor caso para todos los problemas en $NP$ . ^{[ 15 ]} En 2003, Bogdanov y Trevisan generalizaron este resultado a reducciones no adaptativas arbitrarias. ^{[ 16 ]} Estos resultados muestran que es improbable que se pueda establecer alguna asociación entre la complejidad en el caso promedio y la complejidad en el peor caso a través de reducciones. ^{[ 3 ]}

Véase también

Referencias

↑ Goldreich, Oded; Vadhan, Salil (diciembre de 2007). "Número especial sobre complejidad en el peor caso frente al caso promedio. Prólogo de los editores" . Complejidad Computacional . 16 (4): 325–330 . doi : 10.1007/s00037-007-0232-y . ISSN 1016-3328 .
^ Cormen , Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. ISBN 978-0-262-03384-8OCLC 311310321
1 2 3 4 5 6 Bogdanov, Andrej; Trevisan, Luca (2006). "Complejidad del caso promedio" . Fundamentos y tendencias en informática teórica . 2 (1): 1– 106. doi : 10.1561/0400000004 . ISSN 1551-305X .
↑ Knuth, Donald (1973). El arte de la programación informática . Vol. 3. Addison-Wesley.
1 2 Levin, Leonid A. (febrero de 1986). "Problemas completos del caso promedio" . SIAM Journal on Computing . 15 (1): 285– 286. doi : 10.1137/0215020 . ISSN 0097-5397 .
1 2 3 Wang, Jie (1997). "Teoría de la complejidad computacional en el caso promedio". En Hemaspaandra, Lane A.; Selman, Alan L. (eds.). Teoría de la complejidad: Retrospectiva II (PDF) . Vol. 2. Springer Science & Business Media. págs. 295–328 .
1 2 3 4 5 6 7 8 9 Arora, Sanjeev; Barak, Boaz (2009). "18. Complejidad del caso promedio: la teoría de Levin". Complejidad computacional: un enfoque moderno . Cambridge; Nueva York: Cambridge University Press.
↑ Gurevich, Yuri (octubre de 1987). «Problemas NP aleatorios completos e incompletos». 28.º Simposio Anual sobre Fundamentos de la Informática (SFCS 1987) . págs. 111-117 . doi : 10.1109/SFCS.1987.14 . ISBN 0-8186-0807-2.
↑ Livne, Noam (diciembre de 2010). "Todos los problemas NP-completos naturales tienen versiones completas en el caso promedio" . Complejidad Computacional . 19 (4): 477–499 . doi : 10.1007/s00037-010-0298-9 . ISSN 1016-3328 .
↑ Goldreich, Oded (2011), «Notas sobre la teoría de Levin de la complejidad en el caso promedio» , en Goldreich, Oded (ed.), Estudios sobre complejidad y criptografía. Miscelánea sobre la interacción entre aleatoriedad y computación , Lecture Notes in Computer Science, vol. 6650, Berlín, Heidelberg: Springer Berlin Heidelberg, pp. 233–247 , doi : 10.1007/978-3-642-22670-0_21 , ISBN 978-3-642-22669-4, consultado el 21 de mayo de 2025
↑ Katz, Jonathan; Lindell, Yehuda (2021). Introducción a la criptografía moderna . Serie de criptografía y seguridad de redes de Chapman & Hall/CRC (3.ª ed.). Boca Raton, FL: CRC Press. ISBN 978-1-351-13303-6.
↑ Yao, Andrew (1977), "Cálculos probabilísticos: Hacia una medida unificada de complejidad", Actas del 18.º Simposio IEEE sobre Fundamentos de la Informática (FOCS) , págs. 222–227 , doi : 10.1109/SFCS.1977.24
↑ R. Impagliazzo y L. Levin, "No hay mejores maneras de generar instancias NP difíciles que elegir uniformemente al azar", en Actas del 31.er Simposio IEEE sobre Fundamentos de la Informática, págs. 812-821, 1990.
↑ Ben-David, S.; Chor, B.; Goldreich, O. (1989). "Sobre la teoría de la complejidad del caso promedio" . Actas del vigésimo primer simposio anual de la ACM sobre Teoría de la Computación - STOC '89 . ACM Press. págs. 204–216 . doi : 10.1145/73007.73027 . ISBN 978-0-89791-307-2.
↑ Feigenbaum, Joan; Fortnow, Lance (octubre de 1993). "Autorreducibilidad aleatoria de conjuntos completos" . SIAM Journal on Computing . 22 (5): 994–1005 . doi : 10.1137/0222061 . ISSN 0097-5397 .
↑ Bogdanov, Andrej; Trevisan, Luca (enero de 2006). "Sobre reducciones del peor caso al caso promedio para problemas NP" . SIAM Journal on Computing . 36 (4): 1119– 1159. doi : 10.1137/S0097539705446974 . ISSN 0097-5397 .

Lecturas adicionales

Presentaciones pedagógicas:

Impagliazzo, R. (1995). «Una visión personal de la complejidad en el caso promedio». Actas de la Décima Conferencia Anual IEEE sobre Estructura en la Teoría de la Complejidad. IEEE Comput. Soc. Press. pp. 134–147 . doi : 10.1109/SCT.1995.514853 . ISBN 978-0-8186-7052-7.
Wang, Jie (1997). "Teoría de la complejidad computacional en el caso promedio". En Hemaspaandra, Lane A.; Selman, Alan L. (eds.). Teoría de la complejidad: Retrospectiva II (PDF) . Vol. 2. Springer Science & Business Media. pp. 295–328 .
Goldreich, Oded (2011), "Complejidad del caso promedio, revisada" (PDF) , en Goldreich, Oded (ed.), Estudios sobre complejidad y criptografía. Miscelánea sobre la interacción entre aleatoriedad y computación , Lecture Notes in Computer Science, vol. 6650, Berlín, Heidelberg: Springer Berlin Heidelberg, pp. 422–450 , doi : 10.1007/978-3-642-22670-0_29 , ISBN 978-3-642-22669-4
Arora, Sanjeev; Barak, Boaz (2009). "18. Complejidad del caso promedio: la teoría de Levin". Complejidad computacional: un enfoque moderno . Cambridge; Nueva York: Cambridge University Press.

La bibliografía sobre la complejidad promedio de los casos incluye los siguientes trabajos:

Levin, Leonid (1986), "Problemas completos de caso promedio", SIAM Journal on Computing , 15 (1): 285–286 , doi : 10.1137/0215020
Franco, John (1986), "Sobre el rendimiento probabilístico de los algoritmos para el problema de satisfacibilidad", Information Processing Letters , 23 (2): 103–106 , doi : 10.1016/0020-0190(86)90051-7...
Flajolet, Philippe ; Vitter, JS (agosto de 1987), Análisis de casos promedio de algoritmos y estructuras de datos , Tech. Informe, Institut National de Recherche en Informatique et en Automatique, BP 105-78153 Le Chesnay Cedex Francia.
Gurevich, Yuri ; Shelah, Saharon (1987), "Tiempo de cálculo esperado para el problema de la trayectoria hamiltoniana ", SIAM Journal on Computing , 16 (3): 486–502 , CiteSeerX 10.1.1.359.8982 , doi : 10.1137/0216034 .
Ben-David, Shai; Chor, Benny ; Goldreich, Oded ; Luby, Michael (1989), "Sobre la teoría de la complejidad del caso promedio", Actas del 21.º Simposio Anual sobre Teoría de la Computación , Asociación para la Maquinaria de Computación , págs. 204-216 .
Gurevich, Yuri (1991), "Completitud de casos promedio", Journal of Computer and System Sciences , 42 (3): 346–398 , doi : 10.1016/0022-0000(91)90007-R , hdl : 2027.42/29307Véase también el borrador de 1989 .
Selman, B.; Mitchell, D.; Levesque, H. ( 1992), "Distribuciones difíciles y fáciles de problemas SAT", Actas de la 10.ª Conferencia Nacional sobre Inteligencia Artificial , págs. 459–465 .
Schuler, Rainer; Yamakami, Tomoyuki (1992), "Complejidad estructural del caso promedio", Actas de Foundations of Software Technology and Theoretical Computer Science , Lecture Notes in Computer Science, vol. 652, Springer-Verlag, pp . 128–139 .
Reischuk, Rüdiger; Schindelhauer, Christian ( 1993), "Complejidad promedio precisa del caso", Actas del 10.º Simposio Anual sobre Aspectos Teóricos de la Informática , págs. 650–661 .
Venkatesan, R.; Rajagopalan, S. (1992), "Intratabilidad del caso promedio de problemas matriciales y diofánticos", Actas del 24.º Simposio Anual sobre Teoría de la Computación , Asociación para la Maquinaria de Computación , págs. 632–642 .
Cox, Jim; Ericson, Lars; Mishra, Bud (1995), La complejidad promedio de casos de la silogística multinivel (PDF) , Informe técnico TR1995-711, Departamento de Ciencias de la Computación de la Universidad de Nueva York.

[gol07-1] Goldreich, Oded; Vadhan, Salil (diciembre de 2007). "Número especial sobre complejidad en el peor caso frente al caso promedio. Prólogo de los editores" . Complejidad Computacional . 16 (4): 325–330 . doi : 10.1007/s00037-007-0232-y . ISSN 1016-3328 .

[clrs-2] Cormen , Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. ISBN 978-0-262-03384-8OCLC 311310321

[bog06-3] 1 2 3 4 5 6 Bogdanov, Andrej; Trevisan, Luca (2006). "Complejidad del caso promedio" . Fundamentos y tendencias en informática teórica . 2 (1): 1– 106. doi : 10.1561/0400000004 . ISSN 1551-305X .

[knu73-4] Knuth, Donald (1973). El arte de la programación informática . Vol. 3. Addison-Wesley.

[levin86-5] 1 2 Levin, Leonid A. (febrero de 1986). "Problemas completos del caso promedio" . SIAM Journal on Computing . 15 (1): 285– 286. doi : 10.1137/0215020 . ISSN 0097-5397 .

[wangsurvey-6] 1 2 3 Wang, Jie (1997). "Teoría de la complejidad computacional en el caso promedio". En Hemaspaandra, Lane A.; Selman, Alan L. (eds.). Teoría de la complejidad: Retrospectiva II (PDF) . Vol. 2. Springer Science & Business Media. págs. 295–328 .

[ab09-7] 1 2 3 4 5 6 7 8 9 Arora, Sanjeev; Barak, Boaz (2009). "18. Complejidad del caso promedio: la teoría de Levin". Complejidad computacional: un enfoque moderno . Cambridge; Nueva York: Cambridge University Press.

[gur87-8] Gurevich, Yuri (octubre de 1987). «Problemas NP aleatorios completos e incompletos». 28.º Simposio Anual sobre Fundamentos de la Informática (SFCS 1987) . págs. 111-117 . doi : 10.1109/SFCS.1987.14 . ISBN 0-8186-0807-2.

[livne06-9] Livne, Noam (diciembre de 2010). "Todos los problemas NP-completos naturales tienen versiones completas en el caso promedio" . Complejidad Computacional . 19 (4): 477–499 . doi : 10.1007/s00037-010-0298-9 . ISSN 1016-3328 .

[gol97-10] Goldreich, Oded (2011), «Notas sobre la teoría de Levin de la complejidad en el caso promedio» , en Goldreich, Oded (ed.), Estudios sobre complejidad y criptografía. Miscelánea sobre la interacción entre aleatoriedad y computación , Lecture Notes in Computer Science, vol. 6650, Berlín, Heidelberg: Springer Berlin Heidelberg, pp. 233–247 , doi : 10.1007/978-3-642-22670-0_21 , ISBN 978-3-642-22669-4, consultado el 21 de mayo de 2025

[katz07-11] Katz, Jonathan; Lindell, Yehuda (2021). Introducción a la criptografía moderna . Serie de criptografía y seguridad de redes de Chapman & Hall/CRC (3.ª ed.). Boca Raton, FL: CRC Press. ISBN 978-1-351-13303-6.

[12] Yao, Andrew (1977), "Cálculos probabilísticos: Hacia una medida unificada de complejidad", Actas del 18.º Simposio IEEE sobre Fundamentos de la Informática (FOCS) , págs. 222–227 , doi : 10.1109/SFCS.1977.24

[imp90-13] R. Impagliazzo y L. Levin, "No hay mejores maneras de generar instancias NP difíciles que elegir uniformemente al azar", en Actas del 31.er Simposio IEEE sobre Fundamentos de la Informática, págs. 812-821, 1990.

[bd92-14] Ben-David, S.; Chor, B.; Goldreich, O. (1989). "Sobre la teoría de la complejidad del caso promedio" . Actas del vigésimo primer simposio anual de la ACM sobre Teoría de la Computación - STOC '89 . ACM Press. págs. 204–216 . doi : 10.1145/73007.73027 . ISBN 978-0-89791-307-2.

[ff93-15] Feigenbaum, Joan; Fortnow, Lance (octubre de 1993). "Autorreducibilidad aleatoria de conjuntos completos" . SIAM Journal on Computing . 22 (5): 994–1005 . doi : 10.1137/0222061 . ISSN 0097-5397 .

[bog03-16] Bogdanov, Andrej; Trevisan, Luca (enero de 2006). "Sobre reducciones del peor caso al caso promedio para problemas NP" . SIAM Journal on Computing . 36 (4): 1119– 1159. doi : 10.1137/S0097539705446974 . ISSN 0097-5397 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[6]

[7]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]