Teoría de la complejidad computacional

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 27 de abril de 2021; las comprobaciones requieren 8 ediciones .

La teoría de la complejidad computacional es una subsección de la informática teórica que estudia la complejidad de los algoritmos para resolver problemas basados en modelos de dispositivos informáticos formalmente definidos . La complejidad de los algoritmos se mide por los recursos requeridos, principalmente la duración de los cálculos o la cantidad de memoria requerida. En algunos casos, se exploran otros grados de complejidad, como el tamaño de los chips o la cantidad de procesadores necesarios para ejecutar algoritmos paralelos .

La teoría de la complejidad computacional no debe confundirse con la teoría de la computabilidad , que se ocupa de la búsqueda de una respuesta a la pregunta de qué problemas se pueden resolver generalmente usando algoritmos . La tarea principal de la investigación en la teoría de la complejidad computacional es clasificar todos los problemas solubles. En particular, se intenta separar el conjunto de problemas con algoritmos de solución eficiente del conjunto de problemas difíciles de resolver.

Resumen

La complejidad computacional de un algoritmo generalmente se expresa en términos del símbolo "0 en mayúsculas", que indica el orden de magnitud de la complejidad computacional. Es solo un término en la expansión de la función de complejidad que crece más rápido a medida que crece n , y todos los términos de orden inferior se ignoran. Por ejemplo, si la complejidad del tiempo es del orden de n 2, entonces se expresa como O(n 2 ) .

La complejidad del tiempo medida de esta manera es independiente de la implementación.

No necesita saber el tiempo exacto de ejecución de las instrucciones individuales, ni el número de bits que representan varias variables, ni siquiera la velocidad del procesador. Una computadora podría ser un 50% más rápida que otra, y una tercera podría tener el doble del ancho del bus de datos, pero la complejidad del algoritmo, medida en orden de magnitud, no cambiaría. Al evaluar algoritmos bastante complejos, todo lo demás puede despreciarse (hasta un factor constante).

La puntuación de complejidad computacional demuestra claramente cómo el tamaño de los datos de entrada afecta los requisitos de tiempo y memoria.

Por ejemplo, si T=O(n), duplicar la entrada también duplicará el tiempo de ejecución del algoritmo . Si T=O(2 n ) , agregar solo un bit a la entrada duplicará el tiempo de ejecución del algoritmo.

El objetivo principal de la teoría de la complejidad es proporcionar mecanismos para clasificar los problemas computacionales de acuerdo con los recursos necesarios para resolverlos. La clasificación no debe depender de un modelo computacional específico, sino evaluar la complejidad intrínseca del problema.

Los recursos que se evalúan, como se señaló anteriormente, pueden ser el tiempo, el espacio de memoria, los bits aleatorios, la cantidad de procesadores, etc., pero generalmente el factor principal es el tiempo y, con menor frecuencia, el espacio.

La teoría considera el tiempo mínimo y la cantidad de memoria para resolver teóricamente una versión compleja del problema en una computadora conocida como máquina de Turing . Una máquina de Turing es una máquina de estado con una cinta de memoria infinita de lectura y escritura. Esto significa que la máquina de Turing es un modelo computacional realista .

Los problemas que se pueden resolver utilizando polinomios : los algoritmos de tiempo son aquellos que se pueden resolver, dados los datos de entrada normales, en un tiempo aceptable (la definición exacta de "aceptable" depende de condiciones específicas).

Los problemas que solo se pueden resolver con algoritmos superpolinomiales de tiempo polinomial son computacionalmente difíciles incluso para valores relativamente pequeños de n.

Turing demostró que algunos problemas son imposibles de resolver. Incluso sin tener en cuenta la complejidad temporal del algoritmo, es imposible crear un algoritmo para resolverlos.

Complejidad asintótica

Designacion	Explicación intuitiva	Definición
$f(n)\en O(g(n))$	$F$ está acotado superiormente por una función (hasta un factor constante) asintóticamente $gramo$	$\existe (C>0),n_{0}:\forall (n>n_{0})\;\|f(n)\|\leq C\|g(n)\|$ o $\existe (C>0),n_{0}:\forall (n>n_{0})\;f(n)\leq Cg(n)$
$f(n)\en \Omega (g(n))$	$F$ está acotado desde abajo por una función (hasta un factor constante) asintóticamente $gramo$	$\existe (C>0),n_{0}:\forall (n>n_{0})\;\|f(n)\|\geq C\|g(n)\|$
$f(n)\en \Theta (g(n))$	$F$ acotado por abajo y por arriba por la función asintóticamente $gramo$	$\existe (C,C'>0),n_{0}:\forall (n>n_{0})\;C\|g(n)\|\leq \|f(n)\|\leq C' \|g(n)\|$
$f(n)\en o(g(n))$	$gramo$ domina asintóticamente $F$	$\forall (C>0)\existe n_{0}:\forall (n>n_{0})\;\|f(n)\|<C\|g(n)\|$
$f(n)\en \omega (g(n))$	$F$ domina asintóticamente $gramo$	$\forall (C>0)\existe n_{0}:\forall (n>n_{0})\;\|f(n)\|>C\|g(n)\|$
${\ estilo de visualización f (n) \ sim g (n)}$	$F$ es equivalente asintóticamente $gramo$	$\lim _{n\to\infty}{\frac {f(n)}{g(n)}}=1$

Complejidades comunes de los algoritmos

Designacion	Explicación	Ejemplos
$O(1)$	Tiempo de actividad constante, independientemente del tamaño de la tarea.	El tiempo esperado de búsqueda de hash.
${\ estilo de visualización O (\ log \ log n)}$	Crecimiento muy lento del tiempo requerido.	Tiempo esperado para ejecutar una búsqueda de elementos de interpolación. $norte$
$O(\log n)$	Crecimiento logarítmico: duplicar el tamaño de la tarea aumenta el tiempo de ejecución en una cantidad constante.	Informática; búsqueda binaria en una matriz de elementos. $norte$
$En)$	Crecimiento lineal: duplicar el tamaño de la tarea también duplicará el tiempo requerido.	Suma / resta de números a partir de números; búsqueda lineal en una matriz de elementos. $norte$ $norte$
$O(n\cdot\log n)$	Crecimiento linealizado: duplicar el tamaño de la tarea duplicará ligeramente el tiempo requerido.	Ordenar por combinación o elementos múltiples; el límite inferior de clasificación con comparación de elementos. $norte$ $norte$
$O(n^{2})$	Crecimiento cuadrático: duplicar el tamaño de la tarea cuadruplica el tiempo requerido.	Algoritmos elementales de clasificación.
$O(n^{3})$	Crecimiento cúbico: duplicar el tamaño de una tarea aumenta el tiempo requerido por un factor de ocho.	Multiplicación de matrices ordinarias.
${\ estilo de visualización O (c ^ {n})}$	Crecimiento exponencial: un aumento en el tamaño de la tarea no conduce a un aumento múltiple en el tiempo requerido; duplicar el tamaño de la tarea eleva al cuadrado el tiempo requerido $una$ ${\ estilo de visualización c-}$	Algunos problemas del viajante de comercio, algoritmos de búsqueda de fuerza bruta.

Clases de dificultad

La clase de complejidad es un conjunto de problemas de reconocimiento para los cuales existen algoritmos que son similares en complejidad computacional. Los problemas se pueden dividir en clases según la complejidad de su solución. Todas las clases de complejidad están en una relación jerárquica: unas contienen a otras. Sin embargo, para la mayoría de las inclusiones, no se sabe si son estrictas. La clase P , que es la más baja, contiene todos los problemas que se pueden resolver en tiempo polinomial. La clase NP incluye todos los problemas que se pueden resolver en tiempo polinomial solo en una máquina de Turing no determinista (esta es una variante de una máquina de Turing regular que puede hacer conjeturas). Tal máquina hace una conjetura sobre la solución del problema, o "adivina bien" probando todas las conjeturas en paralelo, y verifica su conjetura en tiempo polinomial.

Clase P

La clase P (del inglés Polynomial) es un conjunto de problemas para los cuales existen algoritmos de solución "rápidos" (cuyo tiempo de ejecución depende polinómicamente del tamaño de los datos de entrada). La clase P está incluida en las clases de algoritmos de complejidad más amplia. Para cualquier lenguaje de programación, puede definir una clase P de manera similar (reemplazando la máquina de Turing en la definición con una implementación del lenguaje de programación). Si el compilador del lenguaje en el que se implementa el algoritmo ralentiza la ejecución del algoritmo en un polinomio (es decir, el tiempo de ejecución del algoritmo en una máquina de Turing es menor que algún polinomio de su tiempo de ejecución en un lenguaje de programación) , entonces la definición de clases P para este lenguaje y para la máquina de Turing son las mismas. El código del lenguaje ensamblador se puede convertir a una máquina de Turing con un poco de desaceleración polinomial, y dado que todos los lenguajes existentes permiten la compilación a ensamblador (nuevamente, con desaceleración polinomial), las definiciones de la clase P para máquinas de Turing y para cualquier lenguaje de programación existente son lo mismo.

Clase NP

La clase NP (del inglés Non-deterministic polynomio) es un conjunto de tareas que se pueden resolver con alguna información adicional (el llamado certificado de solución), es decir, la capacidad de "rápidamente" (en un tiempo que no exceda el polinomio del tamaño de los datos) verifique la solución para la máquina de Turing. De manera equivalente, la clase NP se puede definir como una colección de problemas que se pueden resolver "rápidamente" en una máquina de Turing no determinista.

La clase NP se define para un conjunto de lenguas, es decir, conjuntos de palabras sobre un alfabeto finito Σ. Un lenguaje L pertenece a la clase NP si existe un predicado de dos lugares de la clase P (es decir, calculado en tiempo polinomial) y una constante tal que para cualquier palabra la condición es equivalente a la condición . $R(x, y)$ $C>0$ $X$ $x\en L$ $\existe y,|y|<|y|$ $C$ $R(x, y)$

Relación entre las clases de complejidad NP y P

En la teoría de algoritmos, la cuestión de la igualdad de las clases de complejidad P y NP ha sido uno de los problemas centrales abiertos durante más de tres décadas. Si se le da una respuesta afirmativa, esto significará que es teóricamente posible resolver muchos problemas complejos mucho más rápido que ahora. De la definición de las clases P y NP se sigue inmediatamente el corolario: . Sin embargo, hasta ahora no se sabe nada sobre el rigor de esta inclusión, es decir, si existe un problema que se encuentra en NP pero no en P. Si tal problema no existe, entonces todos los problemas que pertenecen a la clase NP pueden resolverse en tiempo polinomial, lo que promete enormes beneficios computacionales. Ahora los problemas más difíciles de la clase NP (los llamados NP - problemas completos) se pueden resolver en tiempo exponencial, lo que casi siempre es inaceptable. En la actualidad, la mayoría de los matemáticos creen que estas clases no son iguales. Según una encuesta de 2002 de 100 científicos, [1] 61 personas pensaron que la respuesta era "no igual"; 9 - "igual"; 22 no contestaron; 8 creen que la hipótesis no se deriva del sistema actual de axiomas y, por lo tanto, no se puede probar ni refutar. De lo anterior se desprende que el problema de estudiar la relación entre las clases P y NP es relevante en la comunidad científica y requiere un análisis más profundo. $P \subseteq NP$

Terquedad

Los problemas que pueden resolverse teóricamente (teniendo un tiempo enorme pero finito), pero que en la práctica toman demasiado tiempo para ser útiles , se denominan intratables .

Historia

Un ejemplo de un análisis temprano de la complejidad de los algoritmos es el análisis del algoritmo de Euclides realizado por Gabriel Lame en 1844.

Al comienzo de la investigación, claramente dedicada al estudio de la complejidad de los algoritmos, muchos investigadores sentaron sus bases teóricas. El más influyente entre ellos fue Alan Turing , quien introdujo el concepto de máquinas de Turing en 1936, que demostraron ser modelos simplificados de computadora flexibles y de gran éxito.

Notas

↑ Gasarch WI "La encuesta P=?NP". / William I. Gasarch Noticias SIGACT. Volumen 33. - 2002 - S. - Modo de acceso: http://www.cs.umd.edu/~gasarch/papers/poll.pdf Copia de archivo fechada el 27 de octubre de 2019 en Wayback Machine - Art. 34-47

Literatura

Christos H. Papadimitriou: Complejidad computacional. Addison-Wesley, Lectura/Mass. 1995, ISBN 0-201-53082-1 .
Lance Fortnow, Steve Homer: Una breve historia de la complejidad computacional. Manuscrito en línea (PDF, 225 kB)
Jan van Leeuwen (Hrsg.): Manual de informática teórica, Volumen A: Algoritmos y complejidad. The MIT Press / Elsevier, Ámsterdam 1994, ISBN 0-262-72020-5 .
Juris Hartmanis , Richard Edwin Stearns : Sobre la complejidad computacional de los algoritmos. En: Trad. Sociedad Matemática Americana. 117/1965, S. 285-306, ISSN 0002-9947 . (Inglés)
Ding-Zhu Du, Ker-I Ko: Teoría de la Complejidad Computacional. John Wiley & Sons, Nueva York 2000, ISBN 0-471-34506-7 .
Michael R. Garey, David S. Johnson: Computadoras e intratabilidad: una guía para la teoría de la integridad NP. Freeman, Nueva York 2003, ISBN 0-7167-1045-5 .
Michael Sipser: Introducción a la Teoría de la Computación. 2. Auflage. Thomson, Boston 2006, ISBN 0-534-95097-3 . (Edición internacional)
Kuzyurin M. M., Fomin S. A. Algoritmos eficientes y complejidad computacional. 2008
Nemirovskiy A. S., Yudin D. B. Complejidad y eficiencia de los métodos de optimización. Moscú: Nauka, 1979
Abramov S. A. Conferencias sobre la complejidad de los algoritmos. - M. , MTsNMO , 2020. - Ed. 3º, rev. y adicional - 256 págs. - ISBN: 978-5-443-91464-0