Complejidad de casos promedio

En la teoría de la complejidad computacional , la complejidad de caso promedio de un algoritmo es la cantidad de algún recurso computacional (típicamente tiempo) usado por el algoritmo, promediado sobre todas las entradas posibles. Con frecuencia se contrasta con la complejidad del peor de los casos, que considera la máxima complejidad del algoritmo en todas las entradas posibles.

Hay tres motivaciones principales para estudiar la complejidad de los casos promedio. ^[1] Primero, aunque algunos problemas pueden ser insolubles en el peor de los casos, las entradas que provocan este comportamiento pueden ocurrir raramente en la práctica, por lo que la complejidad promedio del caso puede ser una medida más precisa del desempeño de un algoritmo. En segundo lugar, el análisis de complejidad de casos promedio proporciona herramientas y técnicas para generar casos concretos de problemas que pueden utilizarse en áreas como la criptografía y la desaleatorización . En tercer lugar, la complejidad de casos promedio permite discriminar el algoritmo más eficiente en la práctica entre los algoritmos de complejidad de casos basados ​​en equivalentes (por ejemplo, Quicksort ).

El análisis de casos promedio requiere una noción de 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 tales algoritmos conduce a la noción relacionada de una complejidad esperada . ^{[2] : 28}

Historia y antecedentes

El rendimiento de caso 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 los algoritmos de tiempo polinómico del peor de los casos. ^[3] En 1973, Donald Knuth ^[4] publicó el Volumen 3 de Art of Computer Programming, que examina extensamente el rendimiento promedio de algoritmos para problemas que se pueden resolver en el peor de los casos polinomiales, como la clasificación y la búsqueda de la mediana.

Un algoritmo eficiente para problemas NP-completos se caracteriza generalmente como uno 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 ineficaz en un número "pequeño" de entradas puede seguir siendo eficaz para "la mayoría" de las entradas que se producen 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 caso más desfavorable y encontrar métodos para relacionar los dos.

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] que} define la complejidad y completitud del caso promedio mientras da un ejemplo de un problema completo para distNP, el análogo de caso promedio de NP .

Definiciones

Complejidad de casos promedio eficiente

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 de caso promedio eficiente como uno que se ejecuta en el tiempo polinomial 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, suponga 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) ² en la entrada x; es decir, B es cuadráticamente más lento que A. Intuitivamente, cualquier definición de eficiencia de 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${\displaystyle n}$, y que A se ejecuta en el tiempo n ² en todas las entradas excepto en la cadena 1 ⁿ para la cual A toma el tiempo 2 ⁿ . Entonces se puede verificar 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 de caso promedio, tiene sentido permitir que un algoritmo A se ejecute más tiempo que el 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 vuelve cada vez más pequeña. Esta intuición se captura en la siguiente fórmula para el tiempo de ejecución polinomial promedio, que equilibra la compensación del polinomio entre el tiempo de ejecución y la fracción de entradas:

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

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. ^[6] Alternativamente, esto se puede escribir como

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

para alguna constante C, 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 todas menos una fracción de las entradas de longitud n, para algunos ε, c> 0. ^{[ 3]}${\displaystyle {\frac {n^{c}}{(t_{A}(n))^{\epsilon }}}}$

Problema de distribución

El siguiente paso es definir la entrada "promedio" para 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" consta de 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 están permitidas son:

1. Distribuciones computables en tiempo polinomial (P-computable): son distribuciones para las que es posible calcular la densidad acumulativa de cualquier entrada x dada. Más formalmente, dada una distribución de probabilidad μ y una cadena x ∈ {0, 1} ⁿ , es posible calcular el valor en tiempo polinómico. Esto implica que Pr [x] también es calculable en tiempo polinomial.${\displaystyle \mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]}$
2. Distribuciones muestreables en tiempo polinómico (P-muestreable): son distribuciones de las que es posible extraer muestras aleatorias en tiempo polinómico.

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]

AvgP y distNP

Un problema de distribución (L, D) está en la clase de complejidad AvgP si existe un algoritmo de caso promedio eficiente para L, como se define anteriormente. En ocasiones, la clase AvgP se denomina distP en la bibliografía. ^[7]

Un problema de distribución (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 casos promedio de P y NP, respectivamente. ^[7]

Reducciones entre problemas de distribución

Sean (L, D) y (L ', D') dos problemas de distribución. (L, D) 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 polinomio de tiempo en ny

1. (Corrección) x ∈ L si y solo si f (x) ∈ L '
2. (Dominación) Hay polinomios pym tales que, para cada n y y, ${\displaystyle \sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(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 tiempo superpolinomial en una pequeña cantidad 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 se produzcan polinomialmente con tanta frecuencia en D '. ^[6]

Problemas de DistNP-completo

El caso promedio análogo a NP-completitud es distNP-completitud. 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 un caso promedio reducible a (L ' , D'). ^[7]

Un ejemplo de un problema distNP-completo es el problema de detención acotado, BH, definido de la siguiente manera:

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

En su artículo original, Levin mostró un ejemplo de un problema de distribución en mosaico que es NP-completo en casos promedio. ^[5] Una encuesta de problemas conocidos de distNP-complete está disponible en línea. ^[6]

Un área de investigación activa implica encontrar nuevos problemas de distNP-completo. Sin embargo, encontrar tales 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 aquella para la que existe un ε> 0 tal que para cualquier x, μ (x) ≤ 2 ^{- | x | ε} .) Un resultado de Livne muestra que todos los problemas naturales NP-completos tienen Versiones completas de DistNP. ^[9] Sin embargo, aún no se ha logrado el objetivo de encontrar un problema de distribución natural que sea DistNP completo. ^[10]

Aplicaciones

Ordenar algoritmos

Como se mencionó anteriormente, gran parte del trabajo inicial relacionado con la complejidad de casos promedio se centró en problemas para los que ya existían algoritmos de tiempo polinómico, 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 ² ), pero un tiempo de ejecución de caso promedio de O (nlog (n)), donde n es la longitud de la entrada que se va a ordenar. ^[2]

Criptografía

Para la mayoría de los problemas, se lleva a cabo un análisis de complejidad de casos promedio para encontrar algoritmos eficientes para un problema que se considera difícil en el peor de los casos. En las aplicaciones criptográficas, sin embargo, 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 es ineficiente. ^[11]

Por 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 registro discreto . Tenga en cuenta 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 mediante entradas aleatorias (es decir, el caso promedio). De hecho, tanto la factorización de enteros como los problemas de logaritmos 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 basa en la existencia de problemas intratables de casos promedio en NP es una de las principales motivaciones para estudiar la complejidad de casos promedio.

Otros resultados

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 naturales sigue siendo una cuestión pendiente 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, muestran que esta conclusión se mantiene bajo un supuesto más débil: si cada idioma 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 existen problemas de 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 del peor caso 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 una asociación entre la complejidad del caso promedio y la complejidad del peor de los casos mediante reducciones. ^[3]

Ver también

• Análisis probabilístico de algoritmos
• Problemas NP-completos
• Complejidad en el peor de los casos

Referencias

1. O. Goldreich y S. Vadhan, Número especial sobre la complejidad del peor de los casos frente a la del caso medio, Comput. Complejo. 16, 325–330, 2007.
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  0-262-03384-4 .
3. A. Bogdanov y L. Trevisan, "Complejidad de casos promedio", Fundamentos y tendencias en la informática teórica, vol. 2, No 1 (2006) 1–106.
4. D. Knuth, El arte de la programación informática . Vol. 3, Addison-Wesley, 1973.
5. L. Levin, "Problemas completos de casos promedio", SIAM Journal on Computing, vol. 15, no. 1, págs. 285-286, 1986.
6. J. Wang, "Teoría de la complejidad computacional de casos promedio", Retrospectiva II de la teoría de la complejidad, págs. 295–328, 1997.
7. S. Arora y B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, Nueva York, NY, 2009.
8. Y. Gurevich, "Problemas NP aleatorios completos e incompletos", Proc. 28th Annual Symp. en Encontrado. of Computer Science, IEEE (1987), págs. 111-117.
9. N. Livne, "Todos los problemas naturales NP-completos tienen versiones completas de casos promedio", Computational Complexity (2010) 19: 477. https://doi.org/10.1007/s00037-010-0298-9
10. O. Goldreich, "Notas sobre la teoría de Levin de la complejidad del caso promedio", Informe técnico TR97-058, Coloquio electrónico sobre complejidad computacional, 1997.
11. 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.
12. R. Impagliazzo y L. Levin, "No hay mejores formas de generar instancias NP duras que seleccionando uniformemente al azar", en Proceedings of the 31st IEEE Sympo- sium on Foundations of Computer Science, págs. 812–821, 1990.
13. S. Ben-David, B. Chor, O. Goldreich y M. Luby, "Sobre la teoría de la complejidad del caso promedio", Revista de Ciencias de la Computación y Sistemas, vol. 44, no. 2, págs. 193-219, 1992.
14. J. Feigenbaum y L. Fortnow, "Auto-reducibilidad aleatoria de conjuntos completos", SIAM Journal on Computing, vol. 22, págs. 994-1005, 1993.
15. A. Bogdanov y L. Trevisan, "En el peor de los casos a reducciones de casos promedio para problemas de NP", en Actas del 44º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación, págs. 308–317, 2003.

Lectura adicional

La literatura de complejidad de casos promedio incluye el siguiente trabajo:

• 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.
• Levin, Leonid (1986), "Problemas completos de casos promedio", SIAM Journal on Computing , 15 (1): 285-286, doi : 10.1137 / 0215020.
• 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 France.
• Gurevich, Yuri ; Shelah, Saharon (1987), "Tiempo de cálculo esperado para el problema de la ruta 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 media de los casos", Proc. 21º Simposio Anual sobre Teoría de la Computación , Asociación de Maquinaria de Computación , págs. 204–216.
• Gurevich, Yuri (1991), " Completitud promedio de casos", Journal of Computer and System Sciences , 42 (3): 346–398, doi : 10.1016 / 0022-0000 (91) 90007-R , hdl : 2027.42 / 29307. Véase también el borrador de 1989 .
• Selman, B .; Mitchell, D .; Levesque, H. (1992), "Distribuciones fáciles y difíciles de problemas SAT", Proc. Décima Conferencia Nacional sobre Inteligencia Artificial , págs. 459–465.
• Schuler, Rainer; Yamakami, Tomoyuki (1992), "Complejidad de caso promedio estructural", Proc. Fundamentos de la tecnología del software y la informática teórica , Lecture Notes in Computer Science, 652 , Springer-Verlag, págs. 128-139.
• Reischuk, Rüdiger; Schindelhauer, Christian (1993), "Complejidad de caso promedio preciso", Proc. Décimo Simposio Anual sobre Aspectos Teóricos de las Ciencias de la Computación , págs. 650–661.
• Venkatesan, R .; Rajagopalan, S. (1992), "Caso promedio intratabilidad de la matriz y problemas diofánticos", Proc. 24º Simposio Anual sobre Teoría de la Computación , Association for Computing Machinery , págs. 632–642.
• Cox, Jim; Ericson, Lars; Mishra, Bud (1995), La complejidad de caso promedio de silogística multinivel (PDF) , Informe técnico TR1995-711, Departamento de Ciencias de la Computación de la Universidad de Nueva York.
• Impagliazzo, Russell (17 de abril de 1995), Una visión personal de la complejidad del caso promedio , Universidad de California, San Diego.
• Paul E. Black, "Θ" , en Dictionary of Algorithms and Data Structures [en línea] Paul E. Black, ed., Instituto Nacional de Estándares y Tecnología de EE. UU. 17 de diciembre de 2004. Consultado el 20 de febrero de 2009.
• Christos Papadimitriou (1994). Complejidad computacional. Addison-Wesley.