Complejidad de caso promedio

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}

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 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 la completitud del caso promedio mientras daba un ejemplo de un problema completo para $distNP$ , el análogo del caso promedio de $NP$ .

Definiciones

Complejidad de caso 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 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:

\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$ , y $ε$ es un valor constante positivo. ^[6] Alternativamente, esto se puede escribir como

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

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]

Problema distributivo

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:

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

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]

AvgP y distNP

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]

Reducciones entre problemas distributivos

Sean $(L, D)$ y $(L', D')$ dos problemas distribucionales. $(L, D)$ el caso promedio se reduce a $(L', D')$ (escrito $(L, D) \leq 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

(Corrección) $x \in L$ si y sólo si $f (x) \in L'$
(Dominación) Hay 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 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]

Problemas de distNP-completos

El análogo en 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 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:

$BH=\{(M,x,1^{t}):M{\text{ is a non-deterministic Turing machine that accepts }}x{\text{ in}}\leq t{\text{ steps}}\}$ ^[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 $distNP$ ^{-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) \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 de distribución natural que sea $DistNP$ -completo aún no se ha logrado. ^[10]

Aplicaciones

Algoritmos de ordenamiento

Como se mencionó anteriormente, gran parte del trabajo inicial relacionado con la complejidad de caso promedio se centró 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]

Criptografía

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 \cap$ $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.

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 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]

Véase también

Referencias

^ O. Goldreich y S. Vadhan, Número especial sobre complejidad del peor caso versus complejidad del caso promedio, Comput. Complex. 16, 325–330, 2007.
^ ab 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 .
^ abcdef A. Bogdanov y L. Trevisan, "Complejidad de caso promedio", Fundamentos y tendencias en ciencias de la computación teórica, vol. 2, n.º 1 (2006) 1–106.
^ D. Knuth, El arte de la programación informática . Vol. 3, Addison-Wesley, 1973.
^ ab L. Levin, "Problemas completos de casos promedio", SIAM Journal on Computing, vol. 15, núm. 1, págs. 285-286, 1986.
^ abc J. Wang, "Teoría de la complejidad computacional de caso promedio", Complexity Theory Retrospective II, págs. 295-328, 1997.
^ abcdefghi S. Arora y B. Barak, Complejidad computacional: un enfoque moderno, Cambridge University Press, Nueva York, NY, 2009.
^ Y. Gurevich, "Problemas NP aleatorios completos e incompletos", Proc. 28.º Simposio Anual sobre Fundamentos de Ciencias de la Computación, IEEE (1987), págs. 111-117.
^ N. Livne, "Todos los problemas NP-completos naturales tienen versiones completas de caso promedio", Computational Complexity (2010) 19:477. https://doi.org/10.1007/s00037-010-0298-9
^ O. Goldreich, "Notas sobre la teoría de la complejidad del caso promedio de Levin", Informe técnico TR97-058, Coloquio electrónico sobre complejidad computacional, 1997.
^ J. Katz e Y. Lindell, Introducción a la criptografía moderna (Serie de criptografía y seguridad de redes Chapman y Hall/CRC), Chapman y Hall/CRC, 2007.
^ R. Impagliazzo y L. Levin, "No hay mejores maneras de generar instancias NP duras que elegir uniformemente al azar", en Actas del 31.º Simposio IEEE sobre fundamentos de la ciencia de la computación, págs. 812-821, 1990.
^ S. Ben-David, B. Chor , O. Goldreich y M. Luby, "Sobre la teoría de la complejidad promedio de los casos", Journal of Computer and System Sciences, vol. 44, núm. 2, págs. 193-219, 1992.
^ J. Feigenbaum y L. Fortnow, "Autorreducibilidad aleatoria de conjuntos completos", SIAM Journal on Computing, vol. 22, págs. 994-1005, 1993.
^ A. Bogdanov y L. Trevisan, "Sobre reducciones del peor caso al caso promedio para problemas 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 sobre complejidad de casos promedio incluye los siguientes trabajos:

Franco, John (1986), "Sobre el desempeño 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 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 de los casos promedio", Proc. 21.° Simposio anual sobre teoría de la computación , Association for Computing Machinery , págs. 204-216.
Gurevich, Yuri (1991), "Completitud de caso promedio", 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 difíciles y fáciles de problemas SAT", Proc. 10th National Conference on Artificial Intelligence , págs. 459–465.
Schuler, Rainer; Yamakami, Tomoyuki (1992), "Complejidad estructural promedio de casos", Proc. Fundamentos de tecnología de software y ciencia informática teórica , Lecture Notes in Computer Science, vol. 652, Springer-Verlag, págs. 128-139.
Reischuk, Rüdiger; Schindelhauer, Christian (1993), "Complejidad de caso promedio precisa", Proc. 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", 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 promedio del caso 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 de los casos promedio, Universidad de California, San Diego.
Paul E. Black, "Θ", en Dictionary of Algorithms and Data Structures[en línea]Paul E. Black, ed., US National Institute of Standards and Technology. 17 de diciembre de 2004. Recuperado el 20 de febrero de 2009.
Christos Papadimitriou (1994). Complejidad computacional. Addison-Wesley.

[gol07-1] O. Goldreich y S. Vadhan, Número especial sobre complejidad del peor caso versus complejidad del caso promedio, Comput. Complex. 16, 325–330, 2007.

[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 0-262-03384-4 .

[bog06-3] A. Bogdanov y L. Trevisan, "Complejidad de caso promedio", Fundamentos y tendencias en ciencias de la computación teórica, vol. 2, n.º 1 (2006) 1–106.

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

[levin86-5] L. Levin, "Problemas completos de casos promedio", SIAM Journal on Computing, vol. 15, núm. 1, págs. 285-286, 1986.

[wangsurvey-6] J. Wang, "Teoría de la complejidad computacional de caso promedio", Complexity Theory Retrospective II, págs. 295-328, 1997.

[ab09-7] S. Arora y B. Barak, Complejidad computacional: un enfoque moderno, Cambridge University Press, Nueva York, NY, 2009.

[gur87-8] Y. Gurevich, "Problemas NP aleatorios completos e incompletos", Proc. 28.º Simposio Anual sobre Fundamentos de Ciencias de la Computación, IEEE (1987), págs. 111-117.

[livne06-9] N. Livne, "Todos los problemas NP-completos naturales tienen versiones completas de caso promedio", Computational Complexity (2010) 19:477. https://doi.org/10.1007/s00037-010-0298-9

[gol97-10] O. Goldreich, "Notas sobre la teoría de la complejidad del caso promedio de Levin", Informe técnico TR97-058, Coloquio electrónico sobre complejidad computacional, 1997.

[katz07-11] J. Katz e Y. Lindell, Introducción a la criptografía moderna (Serie de criptografía y seguridad de redes Chapman y Hall/CRC), Chapman y Hall/CRC, 2007.

[imp90-12] R. Impagliazzo y L. Levin, "No hay mejores maneras de generar instancias NP duras que elegir uniformemente al azar", en Actas del 31.º Simposio IEEE sobre fundamentos de la ciencia de la computación, págs. 812-821, 1990.

[bd92-13] S. Ben-David, B. Chor , O. Goldreich y M. Luby, "Sobre la teoría de la complejidad promedio de los casos", Journal of Computer and System Sciences, vol. 44, núm. 2, págs. 193-219, 1992.

[ff93-14] J. Feigenbaum y L. Fortnow, "Autorreducibilidad aleatoria de conjuntos completos", SIAM Journal on Computing, vol. 22, págs. 994-1005, 1993.

[bog03-15] A. Bogdanov y L. Trevisan, "Sobre reducciones del peor caso al caso promedio para problemas NP", en Actas del 44º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación, págs. 308-317, 2003.