Teoría de la complejidad computacional

En informática y matemáticas teóricas, la teoría de la complejidad computacional se centra en clasificar los problemas computacionales según el uso de recursos y 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.

Se considera que un problema es intrínsecamente difícil si su solución requiere recursos significativos, independientemente del algoritmo utilizado. La teoría formaliza esta intuición al introducir modelos matemáticos de computación para estudiar estos problemas y cuantificar 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 (utilizada en la complejidad de la comunicación), la cantidad de puertas en un circuito (utilizada en la complejidad del circuito) y la cantidad de procesadores (utilizada en la computación paralela). Uno de los roles 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, está dedicado al campo de la complejidad computacional.

Los 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 en particular para resolver un problema, mientras que la segunda hace una pregunta más general sobre todos los algoritmos posibles que podrían usarse para resolver problemas. resolver el mismo problema. Más precisamente, la teoría de la complejidad computacional trata de 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: la última teoría pregunta qué tipo de problemas pueden, en principio, resolverse algorítmicamente.

Problemas computacionales

Un vendedor viaja a través de 14 ciudades alemanas.

Instancias problemáticas

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 denomina instancia del 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. En contraste, una instancia de este problema es un enunciado bastante concreto, que puede servir como entrada para un problema de decisión. Por ejemplo, considere el problema de las pruebas de primalidad. La instancia es un número (por ejemplo, 15) y la solución es "sí" si el número es primo y "no" de lo 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 una instancia, considere la siguiente instancia de la versión de decisión del problema del viajante de comercio: ¿Hay una ruta de 2000 kilómetros como máximo que pase por las 15 ciudades más grandes de Alemania? ? La respuesta cuantitativa a esta instancia particular del problema es de poca utilidad para resolver otras instancias del problema, como pedir un viaje de ida y vuelta a través de todos los sitios en Milán cuya longitud total sea como máximo 10 km. Por esta razón, la teoría de la complejidad aborda problemas computacionales y no instancias de problemas particulares.

Representación de instancias de problemas

Al considerar 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 que no sean 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 demostraciones de teoremas teóricos de la complejidad suelen asumir alguna elección concreta de codificación de entrada, uno intenta mantener la discusión lo suficientemente abstracta como para ser independiente de la elección de codificación. Esto se puede lograr asegurando que las diferentes representaciones se puedan transformar entre sí de manera eficiente.

Problemas de decisión como lenguajes formales

Un problema de decisión sólo tiene dos productos posibles, Sí. o no (o alternativamente 1 o 0) en cualquier entrada.

Los problemas de decisión son uno de los objetos centrales de estudio en 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 cuya salida es sí, y los no miembros son aquellas instancias cuya salida es no. El objetivo es decidir, con la ayuda de un algoritmo, si una cadena de entrada dada es miembro del lenguaje formal en 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, uno tiene que decidir cómo se codifican los gráficos como cadenas binarias.

Problemas de funcionamiento

Un problema de función es un problema computacional en el que se espera una sola salida (de una función total) para cada entrada, pero la salida es más compleja que la de un problema de decisión, es decir, la salida no es solo si o no. Ejemplos notables incluyen el problema del viajante de comercio y el problema de factorización de 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 enteros se puede expresar como el conjunto de triples (a, b, c) tales que la relación a × b = c se mantiene. Decidir si un triple dado es miembro de este conjunto corresponde a resolver el problema de multiplicar dos números.

Medición del tamaño de una instancia

Para medir la dificultad de resolver un problema computacional, es posible que desee 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, las instancias 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. Esto generalmente se toma como 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 un gráfico es conexo, ¿cuánto tiempo más lleva resolver un problema para un gráfico con 2n vértices en comparación con el tiempo que lleva resolver un gráfico 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 empleado en diferentes entradas del mismo tamaño puede ser diferente, la complejidad temporal T(n) en el peor de los casos se define como el tiempo máximo empleado en todas las entradas de tamaño n< /i>. 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.

Modelos de máquinas y medidas de complejidad

Máquina de Turing

Una ilustración de una máquina de Turing

Una máquina de Turing es un modelo matemático de una máquina informática general. Es 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 una máquina informática, 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, esta 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 un 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.

Muchos tipos de máquinas de Turing se utilizan para definir clases de complejidad, como máquinas de Turing deterministas, máquinas de Turing probabilísticas, máquinas de Turing no deterministas, máquinas de Turing cuánticas, máquinas de Turing simétricas y máquinas de Turing alternas. Todos son igualmente poderosos en principio, pero cuando los recursos (como el tiempo o el espacio) son 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 dado. Una forma de ver el no determinismo es que la máquina de Turing se bifurca en muchos caminos 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 solo una máquina abstracta teóricamente interesante que da lugar a clases de complejidad particularmente interesantes. Para ver ejemplos, consulte algoritmo no determinista.

Otros modelos de máquinas

En la bibliografía se han propuesto muchos modelos de máquinas diferentes de las máquinas de Turing multicinta estándar, por ejemplo, máquinas de acceso aleatorio. Quizás sorprendentemente, cada uno de estos modelos se puede convertir a otro sin proporcionar ningún poder computacional adicional. El consumo de tiempo y memoria de estos modelos alternativos puede variar. 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 que puede ramificarse para verificar muchas posibilidades diferentes a la vez. La máquina de Turing no determinista tiene muy poco que ver con la forma en que queremos computar algoritmos físicamente, 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 para analizar problemas computacionales..

Medidas de complejidad

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 de Turing determinista. El tiempo requerido por una máquina de Turing determinista 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 emite 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 la entrada de longitud n es como mucho f(n). Un problema de decisión A se puede resolver en el tiempo f(n) si existe una máquina de Turing operando en el tiempo f(n) que resuelve el problema. Dado que la teoría de la complejidad está interesada en clasificar los 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 dentro del 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 se definen muy generalmente por 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 mediante la notación O grande.

Complejidad de caso mejor, peor y promedio

Visualización del algoritmo de la gama rápida que tiene un rendimiento promedio de caso ${displaystyle {mathcal {}(nlog n)}$.

La complejidad del caso 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:

1. La mejor complejidad: Esta es la complejidad de resolver el problema para la mejor entrada de tamaño n.
2. Complejidad media: Esta es la complejidad de resolver el problema en promedio. Esta complejidad sólo se define con respecto a una distribución de probabilidad sobre los insumos. Por ejemplo, si se supone que todos los insumos del mismo tamaño son igualmente propensos a aparecer, se puede definir la complejidad promedio de los casos con respecto a la distribución uniforme sobre todos los insumos de tamaño n.
3. Análisis amortizado: El análisis amortizado considera tanto las operaciones costosas como menos costosas juntas en toda la serie de operaciones del algoritmo.
4. Complejidad peor: Esta es la complejidad de resolver el problema para la peor entrada de tamaño n.

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 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 tiempo O(n²). Si asumimos que todas las permutaciones posibles de la lista de entrada son igualmente probables, el tiempo promedio que se tarda en ordenar es O(n log n). El mejor de los casos ocurre cuando cada pivote divide la lista por la mitad, y también necesita O(n log n) de tiempo.

Límites superior e inferior de la complejidad de los problemas

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 toma como la complejidad del peor de los casos, a menos que se especifique lo contrario. El análisis de un algoritmo en particular cae dentro del campo de análisis de algoritmos. Para mostrar un límite superior T(n) en la complejidad temporal de un problema, solo se necesita mostrar que hay un algoritmo particular con tiempo de ejecución como máximo T(n). Sin embargo, probar los límites inferiores es mucho más difícil, ya que los límites inferiores hacen una declaración sobre todos los algoritmos posibles que resuelven un problema dado. La frase "todos los algoritmos posibles" incluye no solo 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 generalmente se expresan usando la notación O mayúscula, 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) = 7n² + 15n + 40, en notación O grande se escribiría T(n) = O(n²).

Clases de complejidad

Definir clases de complejidad

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:

• El tipo de problema computacional: Los problemas más utilizados son problemas de decisión. Sin embargo, las clases de complejidad se pueden definir sobre la base de problemas de función, contando problemas, problemas de optimización, problemas de promesa, etc.
• El modelo de cálculo: El modelo más común de computación es la máquina de Turing determinista, pero muchas clases de complejidad se basan en máquinas de Turing no deterministas, circuitos booleanos, máquinas de Turing cuántica, circuitos monotonales, etc.
• El recurso (o recursos) que está siendo limitado y el límite: Estas dos propiedades generalmente se declaran juntas, como "tiempo polímico", "espacio logarítmico", "profundidad constante", etc.

Algunas clases de complejidad tienen definiciones complicadas que no encajan en este marco. Por lo tanto, una clase de complejidad típica tiene una definición como la siguiente:

El conjunto de problemas de decisión solvable por una máquina de Turing determinista dentro del tiempo f()n). (Esta clase de complejidad se conoce como DTIME(f()n)).

Pero limitar el tiempo de cálculo anterior por 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 polinómicas en el tiempo de ejecución, la tesis de Cobham-Edmonds establece que "las complejidades temporales en dos modelos razonables y generales de computación están relacionadas polinómicamente". (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 función es FP.

Clases de complejidad importantes

Representación de la relación entre las clases de complejidad

Se pueden definir muchas clases de complejidad importantes delimitando el tiempo o el espacio que utiliza el algoritmo. Algunas clases importantes de complejidad de los 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 por el teorema de Savitch.

Otras clases de complejidad importantes incluyen BPP, ZPP y RP, que se definen mediante máquinas de Turing probabilísticas; AC y NC, que se definen mediante circuitos booleanos; y BQP y QMA, que se definen utilizando máquinas cuánticas de Turing. #P es una clase de complejidad importante de problemas de conteo (no problemas de decisión). Las clases como IP y AM se definen mediante sistemas de prueba interactivos. ALL es la clase de todos los problemas de decisión.

Teoremas de jerarquía

Para las clases de complejidad definidas de esta manera, es deseable demostrar que relajar los requisitos en (digamos) el tiempo de cálculo define un conjunto mayor de problemas. En particular, aunque DTIME(n) está contenido en DTIME(n²), sería interesante saber si la inclusión es estricta. Para los requisitos de tiempo y espacio, la respuesta a tales preguntas está 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 lo tanto, hay pares de clases de complejidad tales que uno está correctamente incluido en el otro. Habiendo deducido estas inclusiones de conjuntos adecuadas, podemos proceder a hacer afirmaciones cuantitativas sobre cuánto más tiempo o espacio adicional se necesita para aumentar el número de problemas que se pueden resolver.

Más precisamente, el teorema de la jerarquía temporal establece que

${bign]}subsetneq {mathsf {big}{big (}f(n)cdot log ^{2}(f(n)} {big)}}} {big}}} {bign)}}}}}}}}$.

El teorema de la jerarquía espacial establece que

${bign]} {bign]}subsetneq {mathsf {f} {big}{big (}f(n)cdot log(f(n)}{big)}}}}}}} {big}}}}}}} {bign)}}$.

Los teoremas de jerarquía de tiempo y espacio forman la base para 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.

Reducción

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. Captura la noción informal de que un problema es a lo sumo 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 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 una reducción de tiempo polinomial. Esto significa que el proceso de reducción toma 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 usar 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 la multiplicación, ya que elevar al cuadrado puede reducirse a la 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 cada problema en C se puede reducir a X. Así 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 usan comúnmente reducciones de tiempo polinomial. 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 es < i>completar para C. Esto significa que X es el problema más difícil en C. (Dado que muchos problemas pueden ser igualmente difíciles, uno podría decir que X es uno de los problemas más difíciles en C.) Así, la clase de problemas NP-completos contiene los problemas más difíciles problemas en NP, en el sentido de que son los que más probabilidades tienen de no estar en P. Debido a que el problema P = NP no se resuelve, pudiendo reducir un problema NP-completo conocido, Π₂, a otro problema, Π₁, indicaría que no existe una solución conocida en tiempo polinomial para Π₁. Esto se debe a que una solución en tiempo polinomial de Π₁ produciría una solución en tiempo polinomial de Π₂. De manera similar, debido a que todos los problemas NP se pueden reducir al conjunto, encontrar un problema NP completo que se pueda resolver en tiempo polinomial significaría que P = NP.

Problemas abiertos importantes

Diagrama de clases de complejidad siempre que P √ NP. La existencia de problemas en NP fuera de P y NP-completo en este caso fue establecida por Ladner.

Problema P versus NP

La clase de complejidad P suele verse como una abstracción matemática que modela aquellas tareas computacionales que admiten un algoritmo eficiente. Esta hipótesis se llama la tesis de Cobham-Edmonds. La clase de complejidad NP, por otro lado, contiene muchos problemas que a las personas les gustaría resolver de manera eficiente, pero para los cuales no se conoce un algoritmo eficiente, como el problema de satisfacibilidad booleano, 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 no deterministas especiales, se observa fácilmente que cada problema en P también es miembro de la clase NP.

La pregunta de si P es igual a NP es una de las preguntas abiertas más importantes en la informática teórica debido a las amplias implicaciones de una solución. 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 y la capacidad de encontrar pruebas formales de teoremas matemáticos puros. El problema P versus NP es uno de los Problemas del Premio del Milenio propuestos por el Clay Mathematics Institute. Hay un premio de US$1,000,000 por resolver el problema.

Problemas en NP que no se sabe que están en P o NP-completo

Ladner demostró que si P ≠ NP entonces existen problemas en NP que tampoco están en P ni NP-completo. Estos problemas se denominan problemas NP-intermedios. El problema del isomorfismo de grafos, el problema del logaritmo discreto y el problema de factorización de 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 gráfico es el problema computacional de determinar si dos gráficos finitos son isomorfos. Un importante problema sin resolver en la teoría de la complejidad es si el problema del isomorfismo gráfico está en P, NP-complete, o NP-intermediate. La respuesta no es conocida, pero se cree que el problema no está completo. Si el isomorfismo gráfico es completo, la jerarquía de tiempo polinomio se colapsa a su segundo nivel. Puesto que se cree ampliamente que la jerarquía polinomio no colapsa a ningún nivel finito, se cree que el isomorfismo gráfico no es completo. El mejor algoritmo para este problema, debido a László Babai y Eugene Luks tiene tiempo de funcionamiento ${displaystyle O(2^{sqrt {nlog n}}}$ para gráficos con n vertices, aunque algún trabajo reciente de Babai ofrece algunas perspectivas potencialmente nuevas sobre esto.

El problema de la factorización entero es el problema computacional de determinar la factorización principal de un entero dado. Frasado como un problema de decisión, es el problema de decidir si la entrada tiene un factor primario menos que k. No se conoce ningún algoritmo de factorización de entero eficiente, y este hecho forma la base de varios sistemas criptográficos modernos, como el algoritmo RSA. El problema de la factorización entero está en NP y dentro co-NP (y incluso en UP y co-UP). Si el problema es NP-complete, la jerarquía de tiempo polinomio colapsará a su primer nivel (es decir, NP igual co-NP). El algoritmo más conocido para la factorización entero es el sieve de campo número general, que toma tiempo ${displaystyle O(e^{sqrt[{3}}{frac {64}{}}}right){sqrt[{3}} {log n)}{sqrt[{3}}{sqrt[{3}}{log log n)}}}}}}}}}}}} {$ a factor un número extraño n. Sin embargo, el algoritmo cuántico más conocido para este problema, algoritmo de Shor, funciona en tiempo polinomio. Desafortunadamente, este hecho no dice mucho sobre dónde está el problema con respecto a las clases de complejidad no cuántica.

Separaciones entre otras clases de complejidad

Se sospecha que muchas clases de complejidad conocidas son desiguales, pero esto no se ha probado. Por ejemplo P ⊆ NP ⊆ PP ⊆ PSPACE, pero es posible que P = PESPACIO. 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.

Del mismo modo, co-NP es la clase que contiene los problemas de complemento (es decir, problemas con las respuestas sí/no invertidas) de problemas de NP. Se cree que NP no es igual a co-NP; sin embargo, aún no se ha probado. 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.

Del mismo modo, 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.

Intratabilidad

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 < b>problema intratable. Por el contrario, un problema que se puede resolver en la práctica se denomina problema tratable, literalmente "un problema que se puede manejar". El término no factible (literalmente "no se puede hacer") a veces se usa indistintamente con intratable, aunque existe el riesgo de confusión con una solución factible en la optimización matemática.

Los problemas tratables se identifican con frecuencia 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 de tiempo polinomial con grado alto o coeficiente principal grande crece rápidamente y puede ser poco práctica para problemas de tamaño práctico; a la inversa, una solución de tiempo exponencial que crece lentamente puede ser práctica con una entrada realista, o una solución que toma mucho tiempo en el peor de los casos puede tomar poco tiempo en la mayoría de los casos o en el caso promedio y, por lo tanto, seguir siendo práctica. Decir que un problema no está en P no implica que todos los grandes casos 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 la aritmética de Presburger no está en P, pero 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 la 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 son generalmente inutilizables en la práctica, considere un programa que realiza 2ⁿ operaciones antes de detenerse. Para n pequeños, digamos 100, y suponiendo, por ejemplo, que la computadora realiza 10¹² operaciones por segundo, el programa se ejecutaría aproximadamente 4 × 10 ¹⁰ años, que es del mismo orden de magnitud que la edad del universo. Incluso con una computadora mucho más rápida, el programa solo sería útil para instancias muy pequeñas y, en ese sentido, la dificultad de un problema es algo independiente del progreso tecnológico. Sin embargo, un algoritmo de tiempo exponencial que toma 1.0001ⁿ operaciones es práctico hasta que n se hace relativamente grande.

Del mismo modo, un algoritmo de tiempo polinomial no siempre es práctico. Si su tiempo de ejecución es, digamos, n¹⁵, no es razonable considerarlo eficiente y sigue siendo inútil excepto en instancias pequeñas. De hecho, en la práctica, incluso los algoritmos n³ o n² suelen ser poco prácticos en problemas de tamaño realista.

Teoría de la complejidad continua

La teoría de la complejidad continua puede referirse a la teoría de la complejidad de problemas que implican 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 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 computación analógica, que utiliza sistemas dinámicos continuos y ecuaciones diferenciales. La teoría de control se puede considerar una forma de computación y las ecuaciones diferenciales se utilizan en el modelado de sistemas de tiempo continuo e híbridos de tiempo continuo discreto.

Historia

Un ejemplo temprano del análisis de la complejidad de los 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 real dedicada explícitamente a la complejidad de los problemas algorítmicos, varios investigadores establecieron numerosos fundamentos. 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 de la complejidad computacional se atribuye al artículo seminal de 1965 "Sobre la complejidad computacional de los algoritmos" por Juris Hartmanis y Richard E. Stearns, que expuso las definiciones de la complejidad del tiempo y la complejidad del espacio, y demostró los teoremas de jerarquía. Además, en 1965 Edmonds sugirió considerar un "bueno" algoritmo para que sea uno con el tiempo de ejecución acotado por un polinomio del tamaño de entrada.

Los artículos anteriores que estudian los problemas que pueden resolver las máquinas de Turing con recursos acotados específicos incluyen la definición de John Myhill de autómatas acotados lineales (Myhill 1960), el estudio de conjuntos rudimentarios de Raymond Smullyan (1961), así como Hisao Artículo de Yamada sobre cálculos en tiempo real (1962). Algo antes, Boris Trakhtenbrot (1956), un pionero en el campo de la URSS, estudió otra medida de complejidad específica. Como él recuerda:

Sin embargo, [mi] interés inicial [en la teoría de la automata] se apartó cada vez más a favor de la complejidad computacional, una emocionante fusión de métodos combinatorios, heredados de la teoría del cambio, con el arsenal conceptual de la teoría de algoritmos. Estas ideas se me habían ocurrido antes en 1955 cuando acudí el término "función de firma", que hoy en día se conoce como "medida de complejidad".

En 1967, Manuel Blum formuló un conjunto de axiomas (ahora conocidos como axiomas de Blum) que especifican las propiedades deseables de las 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 con esta idea con su artículo histórico, 'Reducibilidad entre problemas combinatorios', en el que demostró que 21 problemas combinatorios y teóricos de grafos diferentes, cada uno de ellos tristemente célebre por su intratabilidad computacional, son NP -completo.

Trabaja en la complejidad

• Wuppuluri, Shyam; Doria, Francisco A., eds. (2020), Unravelling Complexity: The Life and Work of Gregory Chaitin, World Scientific, doi:10.1142/11270, ISBN 978-981-12-0006-9, S2CID 198790362