En informática teórica y matemáticas , la teoría de la complejidad computacional se centra en clasificar los problemas computacionales según su uso de recursos y en relacionar estas clases entre sí. Un problema computacional es una tarea resuelta por una computadora. Un problema de cálculo se puede resolver mediante la aplicación mecánica de pasos matemáticos, como un algoritmo .
Un problema se considera intrínsecamente difícil si su solución requiere importantes recursos, cualquiera que sea el algoritmo utilizado. La teoría formaliza esta intuición, introduciendo modelos matemáticos de computación para estudiar estos problemas y cuantificando su complejidad computacional , es decir, la cantidad de recursos necesarios para resolverlos, como el tiempo y el almacenamiento. También se utilizan otras medidas de complejidad, como la cantidad de comunicación (usada en complejidad de comunicación ), la cantidad de puertas en un circuito (usada en complejidad de circuito ) y la cantidad de procesadores (usados en computación paralela ). Una de las funciones de la teoría de la complejidad computacional es determinar los límites prácticos de lo que las computadoras pueden y no pueden hacer. El problema P versus NP , uno de los siete Problemas del Premio del Milenio , [1] forma parte del campo de la complejidad computacional.
Campos estrechamente relacionados en la informática teórica son el análisis de algoritmos y la teoría de la computabilidad . Una distinción clave entre el análisis de algoritmos y la teoría de la complejidad computacional es que el primero se dedica a analizar la cantidad de recursos que necesita un algoritmo particular para resolver un problema, mientras que el segundo plantea una pregunta más general sobre todos los algoritmos posibles que podrían usarse para resolver un problema. resolver el mismo problema. Más precisamente, la teoría de la complejidad computacional intenta clasificar problemas que pueden o no resolverse con recursos adecuadamente restringidos. A su vez, imponer restricciones a los recursos disponibles es lo que distingue la complejidad computacional de la teoría de la computabilidad: esta última teoría pregunta qué tipos de problemas pueden, en principio, resolverse algorítmicamente.
Un problema computacional puede verse como una colección infinita de instancias junto con un conjunto (posiblemente vacío) de soluciones para cada instancia. La cadena de entrada para un problema computacional se conoce como instancia de problema y no debe confundirse con el problema en sí. En la teoría de la complejidad computacional, un problema se refiere a la cuestión abstracta a resolver. Por el contrario, un ejemplo de este problema es un enunciado bastante concreto, que puede servir como insumo para un problema de decisión. Por ejemplo, consideremos el problema de las pruebas de primalidad . El caso es un número (por ejemplo, 15) y la solución es "sí" si el número es primo y "no" en caso contrario (en este caso, 15 no es primo y la respuesta es "no"). Dicho de otra manera, la instancia es una entrada particular al problema y la solución es la salida correspondiente a la entrada dada.
Para resaltar aún más la diferencia entre un problema y un caso, considere el siguiente ejemplo de la versión de decisión del problema del viajante : ¿Existe una ruta de como máximo 2000 kilómetros que pase por las 15 ciudades más grandes de Alemania? La respuesta cuantitativa a este caso particular del problema es de poca utilidad para resolver otros casos del problema, como pedir un viaje de ida y vuelta a través de todos los sitios de Milán cuya longitud total sea como máximo de 10 km. Por esta razón, la teoría de la complejidad aborda problemas computacionales y no instancias de problemas particulares.
Cuando se consideran problemas computacionales, una instancia de problema es una cadena sobre un alfabeto . Por lo general, se considera que el alfabeto es el alfabeto binario (es decir, el conjunto {0,1}) y, por lo tanto, las cadenas son cadenas de bits . Como en una computadora del mundo real , los objetos matemáticos distintos de las cadenas de bits deben codificarse adecuadamente. Por ejemplo, los números enteros se pueden representar en notación binaria y los gráficos se pueden codificar directamente a través de sus matrices de adyacencia o codificando sus listas de adyacencia en binario.
Aunque algunas pruebas de teoremas de la teoría de la complejidad asumen regularmente alguna elección concreta de codificación de entrada, se intenta mantener la discusión lo suficientemente abstracta como para ser independiente de la elección de codificación. Esto se puede lograr garantizando que las diferentes representaciones puedan transformarse entre sí de manera eficiente.
Los problemas de decisión son uno de los objetos centrales de estudio de la teoría de la complejidad computacional. Un problema de decisión es un tipo especial de problema computacional cuya respuesta es sí o no , o alternativamente 1 o 0. Un problema de decisión puede verse como un lenguaje formal , donde los miembros del lenguaje son instancias cuyo resultado es sí, y los no miembros son aquellas instancias cuyo resultado es no. El objetivo es decidir, con la ayuda de un algoritmo , si una cadena de entrada determinada es miembro del lenguaje formal bajo consideración. Si el algoritmo que decide este problema devuelve la respuesta sí , se dice que el algoritmo acepta la cadena de entrada; de lo contrario, se dice que rechaza la entrada.
Un ejemplo de un problema de decisión es el siguiente. La entrada es un gráfico arbitrario . El problema consiste en decidir si la gráfica dada es conexa o no. El lenguaje formal asociado con este problema de decisión es entonces el conjunto de todos los gráficos conectados; para obtener una definición precisa de este lenguaje, hay que decidir cómo se codifican los gráficos como cadenas binarias.
Un problema de función es un problema computacional en el que se espera un único resultado (de una función total ) para cada entrada, pero el resultado es más complejo que el de un problema de decisión ; es decir, el resultado no es simplemente sí o no. Ejemplos notables incluyen el problema del viajante y el problema de factorización de números enteros .
Es tentador pensar que la noción de problemas de función es mucho más rica que la noción de problemas de decisión. Sin embargo, este no es realmente el caso, ya que los problemas de función pueden reformularse como problemas de decisión. Por ejemplo, la multiplicación de dos números enteros se puede expresar como el conjunto de tripletes ( a , b , c ) tales que se cumple la relación a × b = c . Decidir si un determinado triple es miembro de este conjunto corresponde a resolver el problema de multiplicar dos números.
Para medir la dificultad de resolver un problema computacional, es posible que deseemos ver cuánto tiempo requiere el mejor algoritmo para resolver el problema. Sin embargo, el tiempo de ejecución puede, en general, depender de la instancia. En particular, los casos más grandes requerirán más tiempo para resolverse. Así, el tiempo necesario para resolver un problema (o el espacio necesario, o cualquier medida de complejidad) se calcula en función del tamaño de la instancia. Generalmente se considera que es el tamaño de la entrada en bits. La teoría de la complejidad está interesada en cómo los algoritmos escalan con un aumento en el tamaño de entrada. Por ejemplo, en el problema de encontrar si una gráfica es conexa, ¿cuánto más tiempo se necesita para resolver un problema para una gráfica con 2 n vértices en comparación con el tiempo necesario para una gráfica con n vértices?
Si el tamaño de entrada es n , el tiempo necesario se puede expresar como una función de n . Dado que el tiempo necesario para diferentes entradas del mismo tamaño puede ser diferente, la complejidad de tiempo en el peor de los casos T( n ) se define como el tiempo máximo necesario para todas las entradas de tamaño n . Si T( n ) es un polinomio en n , entonces se dice que el algoritmo es un algoritmo de tiempo polinomial . La tesis de Cobham sostiene que un problema puede resolverse con una cantidad factible de recursos si admite un algoritmo de tiempo polinomial.
Una máquina de Turing es un modelo matemático de una máquina informática general. Se trata de un dispositivo teórico que manipula símbolos contenidos en una tira de cinta. Las máquinas de Turing no pretenden ser una tecnología informática práctica, sino más bien un modelo general de máquina informática: cualquier cosa, desde una supercomputadora avanzada hasta un matemático con lápiz y papel. Se cree que si un problema puede resolverse mediante un algoritmo, existe una máquina de Turing que resuelve el problema. De hecho, ésta es la afirmación de la tesis de Church-Turing . Además, se sabe que todo lo que se puede calcular en otros modelos de computación que conocemos hoy en día, como una máquina RAM , el Juego de la vida de Conway , autómatas celulares , cálculo lambda o cualquier lenguaje de programación, se puede calcular en una máquina de Turing. Dado que las máquinas de Turing son fáciles de analizar matemáticamente y se cree que son tan poderosas como cualquier otro modelo de computación, la máquina de Turing es el modelo más utilizado en la teoría de la complejidad.
Se utilizan muchos tipos de máquinas de Turing para definir clases de complejidad, como las máquinas de Turing deterministas , las máquinas de Turing probabilísticas , las máquinas de Turing no deterministas , las máquinas de Turing cuánticas , las máquinas de Turing simétricas y las máquinas de Turing alternas . En principio, todos son igualmente poderosos, pero cuando los recursos (como el tiempo o el espacio) están limitados, algunos de ellos pueden ser más poderosos que otros.
Una máquina de Turing determinista es la máquina de Turing más básica, que utiliza un conjunto fijo de reglas para determinar sus acciones futuras. Una máquina de Turing probabilística es una máquina de Turing determinista con un suministro adicional de bits aleatorios. La capacidad de tomar decisiones probabilísticas a menudo ayuda a los algoritmos a resolver problemas de manera más eficiente. Los algoritmos que utilizan bits aleatorios se denominan algoritmos aleatorios . Una máquina de Turing no determinista es una máquina de Turing determinista con una característica adicional de no determinismo, que permite que una máquina de Turing tenga múltiples acciones futuras posibles desde un estado determinado. Una forma de ver el no determinismo es que la máquina de Turing se ramifica en muchas rutas computacionales posibles en cada paso, y si resuelve el problema en cualquiera de estas ramas, se dice que ha resuelto el problema. Claramente, este modelo no pretende ser un modelo físicamente realizable, es simplemente una máquina abstracta teóricamente interesante que da lugar a clases de complejidad particularmente interesantes. Para ver ejemplos, consulte algoritmo no determinista .
En la literatura se han propuesto muchos modelos de máquinas diferentes de las máquinas de Turing estándar de cintas múltiples , por ejemplo , máquinas de acceso aleatorio . Quizás resulte sorprendente que cada uno de estos modelos se pueda convertir en otro sin proporcionar ninguna potencia computacional adicional. El consumo de tiempo y memoria de estos modelos alternativos puede variar. [2] Lo que todos estos modelos tienen en común es que las máquinas funcionan de forma determinista .
Sin embargo, algunos problemas computacionales son más fáciles de analizar en términos de recursos más inusuales. Por ejemplo, una máquina de Turing no determinista es un modelo computacional al que se le permite diversificarse para comprobar muchas posibilidades diferentes a la vez. La máquina de Turing no determinista tiene muy poco que ver con cómo queremos calcular físicamente los algoritmos, pero su ramificación captura exactamente muchos de los modelos matemáticos que queremos analizar, por lo que el tiempo no determinista es un recurso muy importante en el análisis de problemas computacionales. .
Para una definición precisa de lo que significa resolver un problema utilizando una determinada cantidad de tiempo y espacio, se utiliza un modelo computacional como la máquina determinista de Turing . El tiempo requerido por una máquina determinista de Turing M en la entrada x es el número total de transiciones de estado, o pasos, que realiza la máquina antes de detenerse y generar la respuesta ("sí" o "no"). Se dice que una máquina de Turing M opera dentro del tiempo f ( n ) si el tiempo requerido por M en cada entrada de longitud n es como máximo f ( n ). Un problema de decisión A se puede resolver en el tiempo f ( n ) si existe una máquina de Turing funcionando en el tiempo f ( n ) que resuelva el problema. Dado que la teoría de la complejidad está interesada en clasificar problemas en función de su dificultad, se definen conjuntos de problemas en función de algunos criterios. Por ejemplo, el conjunto de problemas que se pueden resolver en el tiempo f ( n ) en una máquina de Turing determinista se denota por DTIME ( f ( n )).
Se pueden hacer definiciones análogas para los requisitos de espacio. Aunque el tiempo y el espacio son los recursos de complejidad más conocidos, cualquier medida de complejidad puede verse como un recurso computacional. Las medidas de complejidad generalmente se definen mediante los axiomas de complejidad de Blum . Otras medidas de complejidad utilizadas en la teoría de la complejidad incluyen la complejidad de la comunicación , la complejidad del circuito y la complejidad del árbol de decisión .
La complejidad de un algoritmo a menudo se expresa utilizando notación O grande .
El caso de complejidad mejor, peor y promedio se refiere a tres formas diferentes de medir la complejidad del tiempo (o cualquier otra medida de complejidad) de diferentes entradas del mismo tamaño. Dado que algunas entradas de tamaño n pueden ser más rápidas de resolver que otras, definimos las siguientes complejidades:
El orden de barato a costoso es: Mejor, promedio (de distribución uniforme discreta ), amortizado, peor.
Por ejemplo, considere el algoritmo de clasificación determinista Quicksort . Esto resuelve el problema de ordenar una lista de números enteros que se proporciona como entrada. El peor de los casos es cuando el pivote es siempre el valor más grande o más pequeño de la lista (por lo que la lista nunca se divide). En este caso el algoritmo toma un tiempo O ( n 2 ). Si asumimos que todas las permutaciones posibles de la lista de entrada son igualmente probables, el tiempo promedio necesario para ordenar es O ( n log n ). El mejor caso ocurre cuando cada pivote divide la lista por la mitad, y también necesita tiempo O ( n log n ).
Para clasificar el tiempo de cálculo (o recursos similares, como el consumo de espacio), es útil demostrar los límites superior e inferior de la cantidad máxima de tiempo requerida por el algoritmo más eficiente para resolver un problema determinado. La complejidad de un algoritmo generalmente se considera su peor complejidad, a menos que se especifique lo contrario. Analizar un algoritmo particular cae dentro del campo del análisis de algoritmos . Para mostrar un límite superior T ( n ) en la complejidad temporal de un problema, solo es necesario mostrar que existe un algoritmo particular con un tiempo de ejecución como máximo T ( n ). Sin embargo, demostrar los límites inferiores es mucho más difícil, ya que los límites inferiores hacen una afirmación sobre todos los algoritmos posibles que resuelven un problema determinado. La frase "todos los algoritmos posibles" incluye no sólo los algoritmos conocidos hoy en día, sino cualquier algoritmo que pueda descubrirse en el futuro. Para mostrar un límite inferior de T ( n ) para un problema es necesario demostrar que ningún algoritmo puede tener una complejidad temporal inferior a T ( n ).
Los límites superior e inferior suelen indicarse utilizando la notación O grande , que oculta factores constantes y términos más pequeños. Esto hace que los límites sean independientes de los detalles específicos del modelo computacional utilizado. Por ejemplo, si T ( n ) = 7 n 2 + 15 n + 40, en notación O grande se escribiría T ( n ) = O ( n 2 ).
Una clase de complejidad es un conjunto de problemas de complejidad relacionada. Las clases de complejidad más simples se definen por los siguientes factores:
Algunas clases de complejidad tienen definiciones complicadas que no encajan en este marco. Por tanto, una clase de complejidad típica tiene una definición como la siguiente:
Pero limitar el tiempo de cálculo anterior mediante alguna función concreta f ( n ) a menudo produce clases de complejidad que dependen del modelo de máquina elegido. Por ejemplo, el idioma { xx | x es cualquier cadena binaria} se puede resolver en tiempo lineal en una máquina de Turing de múltiples cintas, pero necesariamente requiere tiempo cuadrático en el modelo de máquinas de Turing de una sola cinta. Si permitimos variaciones polinomiales en el tiempo de ejecución, la tesis de Cobham-Edmond establece que "las complejidades temporales en dos modelos de cálculo generales y razonables están polinómicamente relacionadas" (Goldreich 2008, Capítulo 1.2). Esto forma la base de la clase de complejidad P , que es el conjunto de problemas de decisión que puede resolver una máquina de Turing determinista en un tiempo polinomial. El conjunto correspondiente de problemas de funciones es FP .
Se pueden definir muchas clases de complejidad importantes limitando el tiempo o el espacio utilizado por el algoritmo. Algunas clases de complejidad importantes de problemas de decisión definidos de esta manera son las siguientes:
Las clases de espacio logarítmico (necesariamente) no tienen en cuenta el espacio necesario para representar el problema.
Resulta que PSPACE = NPSPACE y EXPSPACE = NEXPSPACE según el teorema de Savitch .
Otras clases de complejidad importantes incluyen BPP , ZPP y RP , que se definen utilizando máquinas probabilísticas de Turing ; AC y NC , que se definen mediante circuitos booleanos; y BQP y QMA , que se definen mediante máquinas cuánticas de Turing. #P es una clase de complejidad importante de problemas de conteo (no problemas de decisión). Clases como IP y AM se definen mediante sistemas de prueba interactivos . ALL es la clase de todos los problemas de decisión.
Para las clases de complejidad definidas de esta manera, es deseable demostrar que relajar los requisitos sobre (digamos) el tiempo de cálculo define de hecho un conjunto mayor de problemas. En particular, aunque DTIME( n ) está contenido en DTIME( n 2 ), sería interesante saber si la inclusión es estricta. Para los requisitos de tiempo y espacio, la respuesta a estas preguntas viene dada por los teoremas de jerarquía de tiempo y espacio, respectivamente. Se denominan teoremas de jerarquía porque inducen una jerarquía adecuada en las clases definidas al restringir los recursos respectivos. Por tanto, existen pares de clases de complejidad tales que una está incluida adecuadamente en la otra. Una vez deducidas tales inclusiones de conjuntos adecuadas, podemos proceder a hacer afirmaciones cuantitativas sobre cuánto tiempo o espacio adicional se necesita para aumentar el número de problemas que pueden resolverse.
Más precisamente, el teorema de la jerarquía temporal establece que
El teorema de la jerarquía espacial establece que
Los teoremas de jerarquía temporal y espacial forman la base de la mayoría de los resultados de separación de clases de complejidad. Por ejemplo, el teorema de la jerarquía temporal nos dice que P está estrictamente contenido en EXPTIME, y el teorema de la jerarquía espacial nos dice que L está estrictamente contenido en PSPACE.
Muchas clases de complejidad se definen utilizando el concepto de reducción. Una reducción es una transformación de un problema en otro problema. Capta la noción informal de que un problema es, como mucho, tan difícil como otro problema. Por ejemplo, si un problema X se puede resolver usando un algoritmo para Y , X no es más difícil que Y , y decimos que X se reduce a Y. Hay muchos tipos diferentes de reducciones, según el método de reducción, como las reducciones de Cook, las reducciones de Karp y las reducciones de Levin, y el límite de la complejidad de las reducciones, como las reducciones de tiempo polinomial o las reducciones de espacio logarítmico .
La reducción más utilizada es la reducción de tiempo polinomial. Esto significa que el proceso de reducción lleva un tiempo polinomial. Por ejemplo, el problema de elevar al cuadrado un número entero se puede reducir al problema de multiplicar dos números enteros. Esto significa que se puede utilizar un algoritmo para multiplicar dos números enteros para elevar al cuadrado un número entero. De hecho, esto se puede hacer dando la misma entrada a ambas entradas del algoritmo de multiplicación. Así vemos que elevar al cuadrado no es más difícil que multiplicar, ya que elevar al cuadrado se puede reducir a multiplicación.
Esto motiva el concepto de que un problema es difícil para una clase de complejidad. Un problema X es difícil para una clase de problemas C si todos los problemas en C pueden reducirse a X. Por tanto, ningún problema en C es más difícil que X , ya que un algoritmo para X nos permite resolver cualquier problema en C. La noción de problemas difíciles depende del tipo de reducción que se utilice. Para clases de complejidad mayores que P, se utilizan comúnmente reducciones de tiempo polinómico. En particular, el conjunto de problemas que son difíciles para NP es el conjunto de problemas NP-difíciles .
Si un problema X está en C y es difícil para C , entonces se dice que X está completo para C. Esto significa que X es el problema más difícil en C. (Dado que muchos problemas pueden ser igualmente difíciles, se podría decir que X es uno de los problemas más difíciles en C ). Por lo tanto, la clase de problemas NP-completos contiene los problemas más difíciles en NP, en el sentido de que son los más probables. no estar en P. Debido a que el problema P = NP no está resuelto, ser capaz de reducir un problema NP completo conocido, Π 2 , a otro problema, Π 1 , indicaría que no existe una solución conocida en tiempo polinomial para Π 1 . Esto se debe a que una solución en tiempo polinomial de Π 1 produciría una solución en tiempo polinomial de Π 2 . De manera similar, debido a que todos los problemas NP se pueden reducir al conjunto, encontrar un problema NP completo que pueda resolverse en tiempo polinomial significaría que P = NP. [3]
La clase de complejidad P se ve a menudo como una abstracción matemática que modela aquellas tareas computacionales que admiten un algoritmo eficiente. Esta hipótesis se denomina tesis de Cobham-Edmonds . La clase de complejidad NP , por otro lado, contiene muchos problemas que a la gente le gustaría resolver de manera eficiente, pero para los cuales no se conoce ningún algoritmo eficiente, como el problema de satisfacibilidad booleana , el problema de la ruta hamiltoniana y el problema de cobertura de vértices . Dado que las máquinas de Turing deterministas son máquinas de Turing especiales no deterministas, se observa fácilmente que cada problema en P también es miembro de la clase NP.
La cuestión de si P es igual a NP es una de las cuestiones abiertas más importantes en la informática teórica debido a las amplias implicaciones de una solución. [3] Si la respuesta es sí, se puede demostrar que muchos problemas importantes tienen soluciones más eficientes. Estos incluyen varios tipos de problemas de programación entera en investigación de operaciones , muchos problemas en logística , predicción de estructuras de proteínas en biología , [5] y la capacidad de encontrar pruebas formales de teoremas de matemáticas puras . [6] El problema P versus NP es uno de los Problemas del Premio del Milenio propuesto por el Clay Mathematics Institute . Hay un premio de 1.000.000 de dólares por resolver el problema. [7]
Ladner demostró que si P ≠ NP , entonces existen problemas en NP que no son ni en P ni en NP-completos . [4] Estos problemas se denominan problemas NP-intermedios . El problema del isomorfismo gráfico , el problema del logaritmo discreto y el problema de factorización de números enteros son ejemplos de problemas que se cree que son NP-intermedios. Son algunos de los pocos problemas NP que no se sabe que estén en P o que sean NP completos .
El problema del isomorfismo de grafos es el problema computacional de determinar si dos grafos finitos son isomórficos . Un problema importante sin resolver en la teoría de la complejidad es si el problema de isomorfismo de grafos está en P , NP-completo o NP-intermedio. Se desconoce la respuesta, pero se cree que el problema al menos no es NP completo. [8] Si el isomorfismo del gráfico es NP-completo, la jerarquía de tiempo polinomial colapsa a su segundo nivel. [9] Dado que se cree ampliamente que la jerarquía polinomial no colapsa a ningún nivel finito, se cree que el isomorfismo del gráfico no es NP-completo. El mejor algoritmo para este problema, obra de László Babai y Eugene Luks , es el tiempo de ejecución para gráficos con n vértices, aunque algunos trabajos recientes de Babai ofrecen algunas perspectivas potencialmente nuevas al respecto. [10]
El problema de factorización de números enteros es el problema computacional de determinar la factorización prima de un número entero dado. Formulado como un problema de decisión, es el problema de decidir si la entrada tiene un factor primo menor que k . No se conoce ningún algoritmo eficiente de factorización de enteros y este hecho constituye la base de varios sistemas criptográficos modernos, como el algoritmo RSA . El problema de factorización de números enteros está en NP y en co-NP (e incluso en UP y co-UP [11] ). Si el problema es NP-completo , la jerarquía de tiempo polinomial colapsará a su primer nivel (es decir, NP será igual a co-NP ). El algoritmo más conocido para la factorización de números enteros es el tamiz de campo numérico general , que toma tiempo [12] para factorizar un número entero impar n . Sin embargo, el algoritmo cuántico más conocido para este problema, el algoritmo de Shor , se ejecuta en tiempo polinómico. Desafortunadamente, este hecho no dice mucho acerca de dónde radica el problema con respecto a las clases de complejidad no cuánticas.
Se sospecha que muchas clases de complejidad conocidas son desiguales, pero esto no se ha demostrado. Por ejemplo P ⊆ NP ⊆ PP ⊆ PSPACE , pero es posible que P = PSPACE . Si P no es igual a NP , entonces P tampoco es igual a PSPACE . Dado que hay muchas clases de complejidad conocidas entre P y PSPACE , como RP , BPP , PP , BQP , MA , PH , etc., es posible que todas estas clases de complejidad colapsen en una sola clase. Demostrar que cualquiera de estas clases es desigual sería un gran avance en la teoría de la complejidad.
En la misma línea, co-NP es la clase que contiene los problemas complementarios (es decir, problemas con las respuestas sí / no invertidas) de los problemas NP . Se cree [13] que NP no es igual a co-NP ; sin embargo, aún no se ha demostrado. Está claro que si estas dos clases de complejidad no son iguales entonces P no es igual a NP , ya que P = co-P . Así, si P = NP tendríamos co-P = co-NP de donde NP = P = co-P = co-NP .
De manera similar, no se sabe si L (el conjunto de todos los problemas que se pueden resolver en el espacio logarítmico) está estrictamente contenido en P o es igual a P. Nuevamente, hay muchas clases de complejidad entre los dos, como NL y NC , y no se sabe si son clases distintas o iguales.
Se sospecha que P y BPP son iguales. Sin embargo, actualmente está abierto si BPP = NEXP .
Un problema que puede resolverse en teoría (por ejemplo, con recursos grandes pero finitos, especialmente tiempo), pero para el cual en la práctica cualquier solución requiere demasiados recursos para ser útil, se conoce como problema.problema intratable .[14]Por el contrario, un problema que puede resolverse en la práctica se denominaproblema tratable , literalmente "un problema que se puede manejar". El términoinviable(literalmente "no se puede hacer") se usa a veces indistintamente conintratable,[15]aunque esto corre el riesgo de confusión con unasolución factibleenoptimización matemática.[dieciséis]
Los problemas manejables se identifican frecuentemente con problemas que tienen soluciones en tiempo polinomial ( P , PTIME ); esto se conoce como la tesis de Cobham-Edmonds . Los problemas que se sabe que son intratables en este sentido incluyen aquellos que son difíciles de EXPTIME . Si NP no es lo mismo que P, entonces los problemas NP-difíciles también son intratables en este sentido.
Sin embargo, esta identificación es inexacta: una solución en tiempo polinomial con un grado grande o un coeficiente principal grande crece rápidamente y puede resultar poco práctica para problemas de tamaño prácticos; por el contrario, una solución de tiempo exponencial que crece lentamente puede ser práctica con datos realistas, o una solución que lleva mucho tiempo en el peor de los casos puede tardar poco en la mayoría de los casos o en el caso promedio y, por lo tanto, sigue siendo práctica. Decir que un problema no está en P no implica que todos los casos grandes del problema sean difíciles o incluso que la mayoría de ellos lo sean. Por ejemplo, se ha demostrado que el problema de decisión en aritmética de Presburger no está en P, sin embargo, se han escrito algoritmos que resuelven el problema en tiempos razonables en la mayoría de los casos. De manera similar, los algoritmos pueden resolver el problema de mochila NP-completo en una amplia gama de tamaños en menos de un tiempo cuadrático y los solucionadores SAT manejan rutinariamente grandes instancias del problema de satisfacibilidad booleano NP-completo .
Para ver por qué los algoritmos de tiempo exponencial generalmente no se pueden utilizar en la práctica, considere un programa que realiza 2 n operaciones antes de detenerse. Para n pequeño , digamos 100, y suponiendo, por ejemplo, que la computadora realiza 10 12 operaciones cada segundo, el programa se ejecutaría durante aproximadamente 4 × 10 10 años, que es el mismo orden de magnitud que la edad del universo . Incluso con una computadora mucho más rápida, el programa sólo sería útil para casos muy pequeños y, en ese sentido, la intratabilidad de un problema es en cierto modo independiente del progreso tecnológico. Sin embargo, un algoritmo de tiempo exponencial que requiere 1,0001 n operaciones es práctico hasta que n sea relativamente grande.
De manera similar, un algoritmo de tiempo polinomial no siempre es práctico. Si su tiempo de ejecución es, digamos, n 15 , no es razonable considerarlo eficiente y sigue siendo inútil excepto en casos pequeños. De hecho, en la práctica, incluso los algoritmos n 3 o n 2 suelen ser poco prácticos en problemas de tamaño realista.
La teoría de la complejidad continua puede referirse a la teoría de la complejidad de problemas que involucran funciones continuas que se aproximan mediante discretizaciones, como se estudia en el análisis numérico . Un enfoque de la teoría de la complejidad del análisis numérico [17] es la complejidad basada en la información .
La teoría de la complejidad continua también puede referirse a la teoría de la complejidad del uso de la computación analógica , que utiliza sistemas dinámicos continuos y ecuaciones diferenciales . [18] La teoría del control puede considerarse una forma de cálculo y las ecuaciones diferenciales se utilizan en el modelado de sistemas de tiempo continuo e híbridos de tiempo discreto-continuo. [19]
Un ejemplo temprano de análisis de complejidad de algoritmos es el análisis del tiempo de ejecución del algoritmo euclidiano realizado por Gabriel Lamé en 1844.
Antes de que comenzara la investigación propiamente dicha dedicada explícitamente a la complejidad de los problemas algorítmicos, varios investigadores sentaron numerosas bases. La más influyente entre ellas fue la definición de máquinas de Turing de Alan Turing en 1936, que resultó ser una simplificación muy robusta y flexible de una computadora.
El comienzo de los estudios sistemáticos en complejidad computacional se atribuye al artículo fundamental de 1965 "Sobre la complejidad computacional de los algoritmos" de Juris Hartmanis y Richard E. Stearns , que expuso las definiciones de complejidad temporal y espacial , y demostró los teoremas de jerarquía. [20] Además, en 1965 Edmonds sugirió considerar un algoritmo "bueno" aquel cuyo tiempo de ejecución está limitado por un polinomio del tamaño de entrada. [21]
Los artículos anteriores que estudian problemas que pueden resolverse mediante máquinas de Turing con recursos acotados específicos incluyen [20] la definición de autómatas acotados lineales de John Myhill (Myhill 1960), el estudio de conjuntos rudimentarios de Raymond Smullyan (1961), así como el artículo de Hisao Yamada. [22] sobre cálculos en tiempo real (1962). Un poco antes, Boris Trakhtenbrot (1956), un pionero en este campo de la URSS, estudió otra medida de complejidad específica. [23] Como él recuerda:
Sin embargo, [mi] interés inicial [en la teoría de los autómatas] fue cada vez más dejado de lado en favor de la complejidad computacional, una apasionante fusión de métodos combinatorios, heredados de la teoría de la conmutación , con el arsenal conceptual de la teoría de los algoritmos. Estas ideas se me habían ocurrido a principios de 1955, cuando acuñé el término "función de señalización", que hoy en día se conoce comúnmente como "medida de complejidad". [24]
En 1967, Manuel Blum formuló un conjunto de axiomas (ahora conocidos como axiomas de Blum ) que especificaban propiedades deseables de medidas de complejidad en el conjunto de funciones computables y demostró un resultado importante, el llamado teorema de aceleración . El campo comenzó a florecer en 1971 cuando Stephen Cook y Leonid Levin demostraron la existencia de problemas prácticamente relevantes que son NP-completos . En 1972, Richard Karp dio un paso adelante en esta idea con su artículo histórico, "Reducibilidad entre problemas combinatorios", en el que demostró que 21 problemas teóricos combinatorios y de grafos diversos , cada uno de ellos infame por su intratabilidad computacional, son NP-completos. [25]
![{\displaystyle O(e^{\left({\sqrt[{3}]{\frac {64}{9}}}\right){\sqrt[{3}]{(\log n)}}{ \sqrt[{3}]{(\log \log n)^{2}}}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d50912fbf223d0bbadd2a028262414397fbee1a9)