En la teoría de la complejidad computacional , la complejidad del caso promedio de un algoritmo es la cantidad de algún recurso computacional (normalmente tiempo) utilizado por el algoritmo, promediado sobre todas las entradas posibles. Con frecuencia se contrasta con la complejidad del peor caso , que considera la complejidad máxima del algoritmo sobre todas las entradas posibles.
Existen tres motivaciones principales para estudiar la complejidad del caso promedio. [1] En primer lugar, aunque algunos problemas pueden ser intratables en el peor de los casos, 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. En segundo lugar, 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 . En tercer lugar, la complejidad del caso promedio permite discriminar el algoritmo más eficiente en la práctica entre algoritmos de complejidad equivalente en el mejor de los casos (por ejemplo, Quicksort ).
El análisis de casos promedio requiere una noción de una entrada "promedio" para un algoritmo, lo que conduce al problema de idear una distribución de probabilidad sobre las entradas. Alternativamente, se puede utilizar un algoritmo aleatorio . El análisis de tales algoritmos conduce a la noción relacionada de una complejidad esperada . [2] : 28
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 informática , que examina en profundidad el rendimiento promedio de los algoritmos para problemas solucionables en el peor de los casos, como la clasificación y la búsqueda de la mediana.
Un algoritmo eficiente para problemas NP -completos se caracteriza generalmente por ser aquel que se ejecuta en tiempo polinomial para todas las entradas; esto es equivalente a requerir una complejidad eficiente en el peor de los casos. Sin embargo, un algoritmo que es ineficiente en un número "pequeño" de entradas puede ser eficiente para la "mayoría" de las entradas que ocurren en la práctica. Por lo tanto, es deseable estudiar las propiedades de estos algoritmos donde la complejidad del caso promedio puede diferir de la complejidad del peor de los casos y encontrar métodos para relacionar las dos.
Las nociones fundamentales de la complejidad del caso promedio fueron desarrolladas por Leonid Levin en 1986 cuando publicó un artículo de una página [5] que definía la complejidad y completitud del caso promedio mientras daba un ejemplo de un problema completo para distNP , el análogo del caso promedio de NP .
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 uno que se ejecuta en el tiempo polinomial esperado sobre todas las entradas posibles. Tal definición tiene varias deficiencias; en particular, no es robusta a los cambios en el modelo computacional. Por ejemplo, supongamos que el algoritmo A se ejecuta en el tiempo t A ( x ) en la entrada x y el algoritmo B se ejecuta en el 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 el tiempo n 2 en todas las entradas excepto la cadena 1 n para la cual A toma tiempo 2 n . Luego 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 la eficiencia en un caso promedio, tiene sentido permitir que un algoritmo A se ejecute durante más tiempo que el polinomio en algunas entradas, pero la fracción de entradas en las que A requiere un tiempo de ejecución cada vez mayor se vuelve cada vez más pequeña. Esta intuición se refleja en la siguiente fórmula para el tiempo de ejecución polinómico promedio, que equilibra la compensación polinómica entre el tiempo de ejecución y la fracción de entradas:
para cada n , t > 0 y polinomio p , donde t A ( x ) denota el tiempo de ejecución del algoritmo A en la entrada x , y ε es un valor constante positivo. [6] Alternativamente, esto se puede escribir como
para algunas constantes C y ε , donde n = | x | . [7] En otras palabras, un algoritmo A tiene una buena complejidad de caso promedio si, después de ejecutarse durante t A ( n ) pasos, A puede resolver todos menos un n c/( t A ( n )) εfracción de entradas de longitud n , para algún ε , c > 0 . [3]
El siguiente paso es definir la entrada "promedio" de un problema en particular. Esto se logra asociando las entradas de cada problema con una distribución de probabilidad particular. Es decir, un problema de "caso promedio" consiste en un lenguaje L y una distribución de probabilidad asociada D que forma el par ( L , D ) . [7] Las dos clases de distribuciones más comunes que se permiten son:
Estas dos formulaciones, aunque similares, no son equivalentes. Si una distribución es P -computable también es P -muestreable, pero lo inverso no es cierto si P ≠ P #P . [7]
Un problema de distribución ( L , D ) pertenece a la clase de complejidad AvgP si existe un algoritmo de caso promedio eficiente para L , como se definió anteriormente. La clase AvgP se denomina ocasionalmente distP en la literatura. [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]
Juntos, AvgP y distNP definen los análogos de caso promedio de P y NP , respectivamente. [7]
Sean ( L , D ) y ( L′ , D′ ) dos problemas distribucionales. ( L , D ) el caso promedio se reduce a ( L′ , D′ ) (escrito ( L , D ) ≤ AvgP ( L′ , D′ ) ) si hay una función f que para cada n , en la entrada x se puede calcular en polinomio de tiempo en n y
La condición de dominación refuerza la noción de que si el problema ( L , D ) es difícil en promedio, entonces ( L′ , D′ ) también es difícil en promedio. Intuitivamente, una reducción debería proporcionar una forma de resolver una instancia x del problema L calculando f ( x ) y alimentando la salida al algoritmo que resuelve L' . Sin la condición de dominación, esto puede no ser posible ya que el algoritmo que resuelve L en tiempo polinomial en promedio puede tomar un tiempo superpolinomial en un pequeño número de entradas pero f puede mapear estas entradas en un conjunto mucho más grande de D' de modo que el algoritmo A' ya no se ejecuta en tiempo polinomial en promedio. La condición de dominación solo permite que tales cadenas ocurran polinomialmente con tanta frecuencia en D' . [6]
El análogo de caso promedio a 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 caso promedio a ( L′ , D′ ) . [7]
Un ejemplo de un problema distNP -completo es el Problema de Detención Acotada, ( BH , D ) (para cualquier D P -computable ) definido de la siguiente manera:
[7]
En su artículo original, Levin mostró un ejemplo de un problema de teselación distribucional que es NP -completo en el caso promedio. [5] Un estudio de problemas NP -completos conocidos está disponible en línea. [6]
Un área de investigación activa implica encontrar nuevos problemas distNP -completos. Sin embargo, encontrar dichos problemas puede ser complicado debido a un resultado de Gurevich que muestra que cualquier problema de distribución con una distribución plana no puede ser distNP -completo a menos que EXP = NEXP . [8] (Una distribución plana μ es una para la cual existe un ε > 0 tal que para cualquier x , μ ( x ) ≤ 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 de distribución natural que sea DistNP -completo aún no se ha logrado. [10]
Como se mencionó anteriormente, muchos de los primeros trabajos relacionados con la complejidad de casos promedio se centraron en problemas para los que ya existían algoritmos de tiempo polinomial, como la clasificación. Por ejemplo, muchos algoritmos de clasificación que utilizan aleatoriedad, como Quicksort , tienen un tiempo de ejecución en el peor de los casos de O( n 2 ) , pero un tiempo de ejecución en el caso promedio de O( n log( n )) , donde n es la longitud de la entrada que se va a clasificar. [2]
En la mayoría de los problemas, se realiza un análisis de la complejidad del 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 del peor de los casos es irrelevante; en cambio, queremos una garantía de que la complejidad del caso promedio de cada 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 haya 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 los problemas de factorización de enteros como los de logaritmo discreto están en NP ∩ coNP y, por lo tanto, no se cree que sean NP -completos. [7] El hecho de que toda la criptografía se base 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.
En 1990, Impagliazzo y Levin demostraron que si existe un algoritmo de caso promedio eficiente 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. [12] La aplicación de esta teoría a los problemas de distribución natural sigue siendo una cuestión abierta pendiente. [3]
En 1992, Ben-David et al. demostraron que si todos los lenguajes en distNP tienen buenos algoritmos de decisión en promedio, también tienen buenos algoritmos de búsqueda en promedio. Además, demostraron que esta conclusión se cumple bajo un supuesto 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. [13] 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 implica la existencia de algoritmos eficientes en el peor de los casos para todos los problemas en NP . [14] En 2003, Bogdanov y Trevisan generalizaron este resultado a reducciones no adaptativas arbitrarias. [15] Estos resultados muestran que es poco probable que se pueda hacer alguna asociación entre la complejidad del caso promedio y la complejidad del peor de los casos a través de reducciones. [3]
La literatura sobre complejidad de casos promedio incluye los siguientes trabajos:
![{\displaystyle \Pr_{x\in_{R}D_{n}}\left[t_{A}(x)\geq t\right]\leq {\frac {p(n)}{t^{\epsilon }}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7045c500135cd3442a32d1be762c21f02c300bd2)
![{\displaystyle E_{x\in_{R}D_{n}}\left[{\frac {t_{A}(x)^{\epsilon }}{n}}\right]\leq C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97edee63746b20f39645d34920067531e4874912)
![{\displaystyle \mu(x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db5ac7dd29e0d54b628eb7141640156de5f1f349)
