Fundamentos de la teoría de la complejidad computacional EITC/IS/CCTF

Debido a que la cantidad de recursos necesarios para ejecutar un algoritmo varía con el tamaño de la entrada, la complejidad generalmente se expresa como una función f(n), donde n es el tamaño de la entrada y f(n) es la complejidad del peor de los casos ( la cantidad máxima de recursos requeridos en todas las entradas de tamaño n) o la complejidad del caso promedio (el promedio de la cantidad de recursos en todas las entradas de tamaño n). El número de operaciones elementales requeridas en una entrada de tamaño n se expresa comúnmente como complejidad de tiempo, donde se cree que las operaciones elementales toman una cantidad de tiempo constante en una computadora en particular y cambian solo por un factor constante cuando se ejecutan en una máquina diferente. La cantidad de memoria requerida por un algoritmo en una entrada de tamaño n se conoce como complejidad espacial.

El tiempo es el recurso más considerado. Cuando el término “complejidad” se usa sin calificativo, generalmente se refiere a la complejidad del tiempo.

Las unidades de tiempo tradicionales (segundos, minutos, etc.) no se emplean en la teoría de la complejidad, ya que dependen demasiado de la computadora elegida y del avance de la tecnología. Por ejemplo, una computadora de hoy puede ejecutar un algoritmo sustancialmente más rápido que una computadora de la década de 1960; sin embargo, esto se debe a los avances tecnológicos en el hardware de la computadora más que a una calidad inherente del algoritmo. El objetivo de la teoría de la complejidad es cuantificar las necesidades de tiempo inherentes de los algoritmos, o las limitaciones de tiempo fundamentales que un algoritmo impondría en cualquier computadora. Esto se logra contando cuántas operaciones básicas se realizan durante el cálculo. Estos procedimientos se conocen comúnmente como pasos porque se considera que toman un tiempo constante en una máquina en particular (es decir, no se ven afectados por la cantidad de entrada).

Otro recurso importante es la cantidad de memoria de la computadora necesaria para realizar algoritmos.

Otro recurso muy utilizado es la cantidad de operaciones aritméticas. En este escenario, se utiliza el término "complejidad aritmética". La complejidad temporal es generalmente el producto de la complejidad aritmética por un factor constante si se conoce una restricción superior sobre el tamaño de la representación binaria de los números que ocurren durante un cálculo.

El tamaño de los números enteros utilizados durante un cálculo no está limitado por muchos métodos y no es realista suponer que las operaciones aritméticas requieren una cantidad fija de tiempo. Como resultado, la complejidad temporal, también conocida como complejidad de bits, puede ser significativamente mayor que la complejidad aritmética. La dificultad aritmética de calcular el determinante de una matriz de enteros nn, por ejemplo, es O(n^3) para técnicas estándar (eliminación gaussiana). Debido a que el tamaño de los coeficientes puede expandirse exponencialmente durante el cálculo, la complejidad de bits de los mismos métodos es exponencial en n. Si estas técnicas se utilizan junto con la aritmética multimodular, la complejidad de bits se puede reducir a O(n^4).

La complejidad de bits, en términos formales, se refiere al número de operaciones en bits requeridas para ejecutar un algoritmo. Equivale a la complejidad temporal hasta un factor constante en la mayoría de los paradigmas de computación. El número de operaciones en palabras de máquina requeridas por las computadoras es proporcional a la complejidad de bits. Para modelos realistas de computación, la complejidad temporal y la complejidad de bits son, por tanto, idénticas.

El recurso que a menudo se considera en la clasificación y búsqueda es la cantidad de comparaciones de entradas. Si los datos están bien ordenados, este es un buen indicador de la complejidad del tiempo.

En todas las entradas potenciales, es imposible contar el número de pasos en un algoritmo. Debido a que la complejidad de una entrada aumenta con su tamaño, comúnmente se representa como una función del tamaño de la entrada n (en bits), por lo que la complejidad es una función de n. Sin embargo, para entradas del mismo tamaño, la complejidad de un algoritmo puede variar sustancialmente. Como resultado, se emplean rutinariamente una variedad de funciones de complejidad.

La complejidad del peor de los casos es la suma de toda la complejidad para todas las entradas de tamaño n, mientras que la complejidad del caso promedio es la suma de toda la complejidad para todas las entradas de tamaño n (esto tiene sentido, ya que el número de entradas posibles de un tamaño dado es finito). Cuando se utiliza el término "complejidad" sin definirlo más, se tiene en cuenta la complejidad temporal del caso más desfavorable.

La complejidad del peor de los casos y del caso promedio son notoriamente difíciles de calcular correctamente. Además, estos valores exactos tienen poca aplicación práctica porque cualquier cambio en la máquina o en el paradigma de cálculo variaría ligeramente la complejidad. Además, el uso de recursos no es importante para valores pequeños de n, por lo que la facilidad de implementación suele ser más atractiva que la baja complejidad para n pequeño.

Por estas razones, se presta mayor atención al comportamiento de la complejidad para n alto, es decir, su comportamiento asintótico cuando n tiende a infinito. Como resultado, la notación O grande se usa comúnmente para indicar complejidad.

Modelos computacionales

La elección de un modelo de cálculo, que consiste en especificar las operaciones esenciales que se realizan en una unidad de tiempo, es importante para determinar la complejidad. A veces se la denomina máquina de Turing multicinta cuando el paradigma de cálculo no se describe específicamente.

Un modelo determinista de computación es aquel en el que los estados subsiguientes de la máquina y las operaciones a realizar están totalmente definidas por el estado anterior. Las funciones recursivas, el cálculo lambda y las máquinas de Turing fueron los primeros modelos deterministas. Las máquinas de acceso aleatorio (también conocidas como máquinas RAM) son un paradigma popular para simular computadoras del mundo real.

Cuando el modelo de cálculo no está definido, generalmente se asume una máquina de Turing multicinta. En las máquinas de Turing multicinta, la complejidad del tiempo es la misma que en las máquinas RAM para la mayoría de los algoritmos, aunque puede ser necesaria una atención considerable en cómo se almacenan los datos en la memoria para lograr esta equivalencia.

Se pueden realizar varias elecciones en algunos pasos del cálculo en un modelo de cálculo no determinista, como las máquinas de Turing no deterministas. En la teoría de la complejidad, todas las opciones factibles se consideran al mismo tiempo, y la complejidad temporal no determinista es la cantidad de tiempo necesaria cuando siempre se toman las mejores decisiones. Para decirlo de otra manera, el cálculo se realiza simultáneamente en tantos procesadores (idénticos) como se requieran, y el tiempo de cálculo no determinista es el tiempo que tarda el primer procesador en completar el cálculo. Este paralelismo se puede utilizar en la computación cuántica mediante el uso de estados entrelazados superpuestos cuando se ejecutan algoritmos cuánticos especializados, como la factorización de Shor de pequeños enteros, por ejemplo.

Incluso si dicho modelo de cálculo no es practicable actualmente, tiene importancia teórica, particularmente en relación con el problema P = NP, que pregunta si las clases de complejidad producidas al usar "tiempo polinomial" y "tiempo polinomial no determinista" como mínimo superior los límites son los mismos. En una computadora determinista, simular un algoritmo NP requiere "tiempo exponencial". Si una tarea se puede resolver en tiempo polinomial en un sistema no determinista, pertenece a la clase de dificultad NP. Si un problema está en NP y no es más fácil que cualquier otro problema de NP, se dice que es NP-completo. El problema de la mochila, el problema del viajante de comercio y el problema de la satisfacibilidad booleana son problemas combinatorios NP-completos. El algoritmo más conocido tiene una complejidad exponencial para todos estos problemas. Si cualquiera de estos problemas pudiera resolverse en tiempo polinomial en una máquina determinista, entonces todos los problemas NP también podrían resolverse en tiempo polinomial, y se establecería P = NP. A partir de 2017, se asume ampliamente que P NP, lo que implica que las peores situaciones de los problemas de NP son fundamentalmente difíciles de resolver, es decir, toman mucho más tiempo que cualquier período de tiempo factible (décadas) dadas longitudes de entrada interesantes.

Computación paralela y distribuida

La computación paralela y distribuida implica dividir el procesamiento entre varios procesadores que funcionan al mismo tiempo. La distinción fundamental entre los distintos modelos es el método de envío de datos entre procesadores. La transmisión de datos entre procesadores suele ser muy rápida en la computación paralela, mientras que la transferencia de datos entre procesadores en la computación distribuida se realiza a través de una red y, por lo tanto, es sustancialmente más lenta.

Un cálculo en N procesadores toma al menos el cociente por N del tiempo que toma en un solo procesador. En realidad, debido a que algunas subtareas no se pueden paralelizar y algunos procesadores pueden necesitar esperar un resultado de otro procesador, este límite teóricamente ideal nunca se alcanzará.

El problema clave de la complejidad es, por lo tanto, desarrollar algoritmos para que el producto del tiempo de cómputo por el número de procesadores sea lo más cercano posible al tiempo requerido para realizar el mismo cálculo en un solo procesador.

Computación cuántica

Una computadora cuántica es una computadora con un modelo de cálculo basado en la mecánica cuántica. La tesis de Church-Turing es válida para las computadoras cuánticas, lo que implica que cualquier problema que una computadora cuántica pueda resolver también puede ser resuelto por una máquina de Turing. Sin embargo, algunas tareas teóricamente podrían resolverse utilizando una computadora cuántica en lugar de una computadora clásica con una complejidad temporal significativamente menor. Por el momento, esto es estrictamente teórico, ya que nadie sabe cómo desarrollar una computadora cuántica práctica.

La teoría de la complejidad cuántica se creó para investigar los diferentes tipos de problemas que pueden resolver las computadoras cuánticas. Se utiliza en la criptografía poscuántica, que es el proceso de creación de protocolos criptográficos que son resistentes a los ataques informáticos cuánticos.

Complejidad del problema (límites inferiores)

El mínimo de las complejidades de los algoritmos que pueden resolver el problema, incluidas las técnicas no descubiertas, es la complejidad del problema. Como resultado, la complejidad de un problema es igual a la complejidad de cualquier algoritmo que lo resuelva.

Como resultado, cualquier complejidad dada en notación O grande representa una complejidad tanto del algoritmo como del problema que lo acompaña.

Por otro lado, la obtención de límites inferiores no triviales sobre la complejidad de un problema suele ser difícil y existen pocas estrategias para hacerlo.

Para resolver la mayoría de los problemas, se deben leer todos los datos de entrada, lo que lleva un tiempo proporcional a la magnitud de los datos. Como resultado, estos problemas tienen al menos una complejidad lineal o, en notación omega grande, una complejidad de Ω(n).

Algunos problemas, como los de álgebra computacional y geometría algebraica computacional, tienen soluciones muy grandes. Debido a que la salida debe escribirse, la complejidad está restringida por el tamaño máximo de la salida.

El número de comparaciones requeridas para un algoritmo de clasificación tiene un límite inferior no lineal de Ω (nlogn). Como resultado, los mejores algoritmos de clasificación son los más eficientes ya que su complejidad es O(nlogn). El hecho de que haya n! maneras de organizar n cosas conduce a este límite inferior. ¡Porque cada comparación divide esta colección de n! órdenes en dos partes, el número de N comparaciones necesarias para distinguir todas las órdenes debe ser 2N > n!, lo que implica O(nlogn) según la fórmula de Stirling.

Reducir un problema a otro problema es una estrategia común para obtener restricciones de complejidad reducida.

Desarrollo de algoritmos

La evaluación de la complejidad de un algoritmo es un elemento importante del proceso de diseño, ya que proporciona información útil sobre el rendimiento que se puede esperar.

Es un malentendido frecuente que, como resultado de la ley de Moore, que predice el crecimiento exponencial de la potencia informática moderna, la evaluación de la complejidad de los algoritmos será menos relevante. Esto es incorrecto porque el aumento de potencia permite el procesamiento de cantidades masivas de datos (big data). Por ejemplo, cualquier algoritmo debería funcionar bien en menos de un segundo al ordenar alfabéticamente una lista de unos pocos cientos de entradas, como la bibliografía de un libro. Por otro lado, para un millón de entradas (por ejemplo, los números de teléfono de una gran ciudad), los algoritmos básicos que requieren comparaciones O(n2) tendrían que realizar un billón de comparaciones, lo que llevaría tres horas a una velocidad de 10 millones de comparaciones por segundo. Quicksort y merge sort, por otro lado, solo requieren comparaciones nlogn (como complejidad de caso promedio para el primero, como complejidad de caso peor para el segundo). Esto produce alrededor de 30,000,000 1,000,000 3 comparaciones para n = 10 XNUMX XNUMX, lo que tomaría solo XNUMX segundos a XNUMX millones de comparaciones por segundo.

Como resultado, evaluar la complejidad puede permitir la eliminación de muchos algoritmos ineficientes antes de la implementación. Esto también se puede usar para ajustar algoritmos complejos sin tener que probar todas las variantes posibles. El estudio de la complejidad permite centrar el esfuerzo en aumentar la eficiencia de una implementación mediante la determinación de los pasos más costosos de un algoritmo complejo.