En la teoría de la complejidad computacional , la complejidad promedio de un algoritmo es la cantidad de algún recurso computacional (generalmente tiempo) utilizado por el algoritmo, promediado sobre todas las entradas posibles. Con frecuencia se contrasta con la complejidad del peor de los casos , que considera la complejidad máxima del algoritmo sobre todas las entradas posibles.
Hay tres motivaciones principales para estudiar la complejidad promedio de los casos. [1] En primer lugar, aunque algunos problemas pueden ser intratables en el peor de los casos, las entradas que provocan este comportamiento rara vez ocurren en la práctica, por lo que la complejidad promedio del caso puede ser una medida más precisa del rendimiento de un algoritmo. En segundo lugar, el análisis de complejidad de casos promedio proporciona herramientas y técnicas para generar casos 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 diseñar 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 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 cuales ya se conocían los algoritmos de tiempo polinomial del 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 exhaustivamente el rendimiento promedio de los algoritmos para problemas que se pueden resolver en el peor de los casos en tiempo polinomial, como la clasificación y la búsqueda de la mediana.
Un algoritmo eficiente para problemas NP -completos generalmente se caracteriza por ser aquel que se ejecuta en tiempo polinomial para todas las entradas; esto equivale a requerir una complejidad eficiente en el peor de los casos. Sin embargo, un algoritmo que sea ineficiente en un número "pequeño" de entradas puede seguir siendo 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 ambas.
Las nociones fundamentales de complejidad de caso promedio fueron desarrolladas por Leonid Levin en 1986 cuando publicó un artículo de una página [5] definiendo la complejidad y la integridad del caso promedio y al mismo tiempo dando un ejemplo de un problema completo para distNP , el análogo de caso promedio de NP .
La primera tarea es definir con precisión qué se entiende por un algoritmo que sea eficiente "en promedio". Un intento inicial podría definir un algoritmo de caso promedio eficiente como uno que se ejecuta en el tiempo polinómico esperado sobre todas las entradas posibles. Esta definición tiene varias deficiencias; en particular, no es robusto 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 captar la idea de que A es eficiente en promedio si y sólo 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 un tiempo n 2 en todas las entradas excepto en la cadena 1 n para la cual A toma un tiempo 2 n . Entonces se puede comprobar fácilmente que el tiempo de ejecución esperado de A es polinómico pero el tiempo de ejecución esperado de B es exponencial. [3]
Para crear una definición más sólida de eficiencia de caso promedio, tiene sentido permitir que un algoritmo A se ejecute durante más tiempo que el polinomial 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 el equilibrio polinómico 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 ejecutar t A ( n ) pasos, A puede resolver todos menos an c/( t A ( norte )) εfracción de entradas de longitud n , para algunos ε , c > 0 . [3]
El siguiente paso es definir la entrada "promedio" para un problema particular. Esto se logra asociando las entradas de cada problema con una distribución de probabilidad particular. Es decir, un problema de "caso promedio" consta de un lenguaje L y una distribución de probabilidad asociada D que forma el par ( L , D ) . [7] Las dos clases más comunes de distribuciones permitidas son:
Estas dos formulaciones, aunque similares, no son equivalentes. Si una distribución es P -computable, también es P -muestreable, pero lo contrario no es cierto si P ≠ P #P . [7]
Un problema distribucional ( L , D ) está en la clase de complejidad AvgP si existe un algoritmo de caso promedio eficiente para L , como se definió anteriormente. La clase AvgP ocasionalmente se denomina distP en la literatura. [7]
Un problema distribucional ( L , D ) está en 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 de distribución. ( 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 puede ser calculado en tiempo polinomio 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 lo es en promedio. Intuitivamente, una reducción debería proporcionar una manera 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 polinómico 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 mayor 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 la misma frecuencia en D' . [6]
El caso promedio análogo a la completitud NP es la completitud distNP . Un problema de distribución ( 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 acotado, BH , definido de la siguiente manera:
[7]
En su artículo original, Levin mostró un ejemplo de un problema de mosaico distributivo que es NP completo en el caso promedio . [5] Una encuesta sobre problemas conocidos de distNP -complete está disponible en línea. [6]
Un área de investigación activa implica encontrar nuevos problemas completos de distNP . Sin embargo, encontrar tales problemas puede resultar complicado debido a un resultado de Gurevich que muestra que cualquier problema distributivo 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 ) ≤ 2 −| x | ε .) Un resultado de Livne muestra que todos los problemas NP completos naturales tienen DistNP -versiones completas. [9] Sin embargo, aún no se ha logrado el objetivo de encontrar un problema de distribución natural que sea DistNP completo. [10]
Como se mencionó anteriormente, muchos de los primeros trabajos relacionados con la complejidad del caso promedio se centraron en problemas para los cuales 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 promedio de O( n log( n )) , donde n es la longitud de la entrada a clasificar. [2]
Para la mayoría de los problemas, se realiza un análisis de 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 promedio de cada algoritmo que "rompe" el esquema criptográfico sea ineficiente. [11]
Así, 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 registro discreto . Tenga en cuenta que no es deseable que la función candidata sea NP -completa ya que esto sólo 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 con entradas aleatorias (es decir, el caso promedio). De hecho, tanto los problemas de factorización de enteros como los de registros discretos 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 de casos promedio en NP es una de las principales motivaciones para estudiar la complejidad de los casos 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 hay un algoritmo de caso promedio para cada problema en NP bajo cualquier distribución muestreable de 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. demostró que si todos los idiomas en distNP tienen algoritmos de decisión buenos en promedio, también tienen algoritmos de búsqueda buenos en promedio. Además, muestran 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 pueden existir sólo 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 demostrar, 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 del peor de los casos. Algoritmos eficientes para todos los problemas en NP . [14] En 2003, Bogdanov y Trevisan generalizaron este resultado a reducciones arbitrarias no adaptativas. [15] Estos resultados muestran que es poco probable que se pueda establecer alguna asociación entre la complejidad del caso promedio y la complejidad del peor de los casos mediante reducciones. [3]
La literatura de complejidad de casos promedio incluye el siguiente trabajo:
![{\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)
