Teoría de la complejidad computacional

Un problema computacional puede considerarse 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 pregunta abstracta que se debe resolver. En cambio, una instancia de este problema es una expresión bastante concreta, que puede servir como entrada para un problema de decisión. Por ejemplo, consideremos el problema de la prueba 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" en caso contrario (en este caso, 15 no es primo y la respuesta es "no"). Dicho de otro modo, la instancia es una entrada particular para el 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 práctico, consideremos el siguiente ejemplo del problema del viajante : ¿Existe una ruta de como máximo 2000 kilómetros que atraviese las 14 ciudades más grandes de Alemania? La respuesta cuantitativa a este caso práctico resulta poco útil para resolver otros casos, como por ejemplo, un viaje de ida y vuelta que recorra 14 lugares en Milán con una longitud total máxima de 10 km. Por esta razón, la teoría de la complejidad aborda problemas computacionales y no casos prácticos específicos.

Al considerar problemas computacionales, una instancia de problema es una cadena sobre un alfabeto . Generalmente, el alfabeto se considera el alfabeto binario (es decir, el conjunto {0,1}), por lo que las cadenas son cadenas de bits . Al igual que en una computadora real , los objetos matemáticos que no son cadenas de bits deben codificarse adecuadamente. Por ejemplo, los números enteros pueden representarse en notación binaria , y los grafos pueden codificarse directamente mediante sus matrices de adyacencia , o codificando sus listas de adyacencia en binario.

Si bien algunas demostraciones de teoremas de la teoría de la complejidad suelen presuponer una codificación de entrada concreta, se procura que la discusión sea lo suficientemente abstracta como para ser independiente de la elección precisa de dicha codificación. Esto se logra asegurando que las diferentes representaciones puedan transformarse eficientemente entre sí.

Los problemas de decisión son uno de los principales objetos de estudio en la teoría de la complejidad computacional. Un problema de decisión es un tipo de problema computacional cuya respuesta es sí o no (o 1 o 0). Un problema de decisión puede considerarse como un lenguaje formal , donde los miembros del lenguaje son instancias cuya salida es sí, y los no miembros son aquellas cuya salida es no. El objetivo es decidir, con la ayuda de un algoritmo , si una cadena de entrada dada pertenece al lenguaje formal en cuestión. Si el algoritmo que resuelve este problema devuelve la respuesta sí , se dice que el algoritmo acepta la cadena de entrada; de lo contrario, se dice que la rechaza.

Un ejemplo de problema de decisión es el siguiente: la entrada es un grafo arbitrario . El problema consiste en decidir si el grafo dado es conexo o no. El lenguaje formal asociado a este problema de decisión es el conjunto de todos los grafos conexos; para obtener una definición precisa de este lenguaje, es necesario decidir cómo se codifican los grafos como cadenas binarias.

Un problema de función es un problema computacional en el que se espera una única salida (de una función total ) para cada entrada, pero la salida puede ser más compleja que la de un problema de decisión ; es decir, la salida no es simplemente sí o no. Ejemplos notables incluyen el problema del viajante y el problema de factorización de enteros .

Resulta 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, esto no es realmente así, ya que los problemas de función pueden reformularse como problemas de decisión. Por ejemplo, la multiplicación de dos enteros puede expresarse como el conjunto de ternas.${\displaystyle (a,b,c)}$de tal manera que la relación${\displaystyle a\times b=c}$Se cumple. Decidir si una terna dada pertenece a este conjunto equivale a resolver el problema de multiplicar dos números.

Para medir la dificultad de resolver un problema computacional, se puede observar cuánto tiempo requiere el mejor algoritmo para resolverlo. 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. Por lo tanto, el tiempo requerido para resolver un problema (o el espacio requerido, o cualquier medida de complejidad) se calcula en función del tamaño de la instancia. El tamaño de entrada se mide típicamente en bits. La teoría de la complejidad estudia cómo escalan los algoritmos a medida que aumenta el tamaño de entrada. Por ejemplo, en el problema de determinar si un grafo está conectado, ¿cuánto más tiempo se necesita para resolver un problema para un grafo con${\displaystyle 2n}$vértices comparados con el tiempo que se tarda en un gráfico con${\displaystyle n}$¿vértices?

Si el tamaño de entrada es${\displaystyle n}$, el tiempo empleado puede expresarse como una función de${\displaystyle n}$Dado que el tiempo empleado en diferentes entradas del mismo tamaño puede ser diferente, la complejidad temporal en el peor de los casos es${\displaystyle T(n)}$se define como el tiempo máximo empleado en todas las entradas de tamaño${\displaystyle n}$. Si${\displaystyle T(n)}$es un polinomio en${\displaystyle 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 y solo si admite un algoritmo de tiempo polinomial.

Una máquina de Turing es un modelo matemático de una máquina de computación general. Es un dispositivo teórico que manipula símbolos contenidos en una tira de cinta. Las máquinas de Turing no están concebidas como una tecnología de computación práctica, sino como un modelo general de una máquina de computación, 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 lo resuelve. 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 conocidos 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 consideran tan potentes como cualquier otro modelo de computación, son el modelo más utilizado en la teoría de la complejidad.

Existen muchos tipos de máquinas de Turing para definir clases de complejidad, como las máquinas de Turing deterministas , probabilísticas , no deterministas , cuánticas , simétricas y alternantes . En principio, todas son igualmente potentes, pero cuando los recursos (como el tiempo o el espacio) son limitados, algunas pueden ser más potentes que otras.

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 la característica adicional del no determinismo, lo que le permite tener múltiples acciones futuras posibles desde un estado dado. 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 lo ha resuelto. Claramente, este modelo no pretende ser un modelo físicamente realizable, sino simplemente una máquina abstracta teóricamente interesante que da lugar a clases de complejidad particularmente interesantes. Para ejemplos, véase algoritmo no determinista .

En la literatura se han propuesto muchos modelos de máquinas diferentes de las máquinas de Turing multitape estándar, por ejemplo , máquinas de acceso aleatorio . Quizás sorprendentemente, cada uno de estos modelos puede convertirse 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 operan de forma determinista .

Sin embargo, algunos problemas computacionales son más fáciles de analizar en términos de recursos menos convencionales. Por ejemplo, una máquina de Turing no determinista es un modelo computacional que puede ramificarse para comprobar simultáneamente diversas posibilidades. Si bien la máquina de Turing no determinista tiene poco que ver con la forma física en que queremos calcular algoritmos, su capacidad de ramificación reproduce con precisión muchos de los modelos matemáticos que deseamos analizar, por lo que el tiempo no determinista se convierte en un recurso fundamental para el análisis de problemas computacionales.

Para una definición precisa de lo que significa resolver un problema utilizando una cantidad determinada 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${\displaystyle M}$en la entrada${\displaystyle x}$es el número total de transiciones de estado, o pasos, que realiza la máquina antes de detenerse y emitir la respuesta ("sí" o "no"). Una máquina de Turing${\displaystyle M}$Se dice que funciona dentro del tiempo${\displaystyle f(n)}$si el tiempo requerido por${\displaystyle M}$en cada entrada de longitud${\displaystyle n}$es como máximo${\displaystyle f(n)}$Un problema de decisión${\displaystyle A}$se puede resolver a tiempo${\displaystyle f(n)}$Si existe una máquina de Turing que funcione en el tiempo${\displaystyle f(n)}$que resuelve el problema. Dado que la teoría de la complejidad se interesa en clasificar los problemas en función de su dificultad, se definen conjuntos de problemas en función de ciertos criterios. Por ejemplo, el conjunto de problemas que se pueden resolver dentro de un tiempo${\displaystyle f(n)}$en una máquina de Turing determinista se denota entonces por DTIME (${\displaystyle f(n)}$).

Se pueden establecer definiciones análogas para los requisitos de espacio. Si bien el tiempo y el espacio son los recursos de complejidad más conocidos, cualquier medida de complejidad puede considerarse un recurso computacional . Las medidas de complejidad se definen generalmente 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 de los circuitos y la complejidad de los árboles de decisión .

La complejidad de un algoritmo se suele expresar utilizando la notación O grande .

La complejidad del mejor, peor y caso promedio se refiere a tres formas diferentes de medir la complejidad temporal (o cualquier otra medida de complejidad) de diferentes entradas del mismo tamaño. Dado que algunas entradas de tamaño${\displaystyle n}$Puede que sea más rápido de resolver que otros, definimos las siguientes complejidades:

1. Complejidad del mejor caso: Esta es la complejidad de resolver el problema para la mejor entrada de tamaño${\displaystyle n}$.
2. Complejidad del caso promedio: Esta es la complejidad de resolver el problema en promedio, para entradas de tamaño n . Esta complejidad solo se define con respecto a una distribución de probabilidad sobre las entradas. Por ejemplo, si se supone que todas las entradas del mismo tamaño tienen la misma probabilidad de aparecer, la complejidad del caso promedio se puede definir con respecto a la distribución uniforme sobre todas las entradas de tamaño${\displaystyle n}$.
3. Análisis amortizado : El análisis amortizado considera tanto las operaciones costosas como las menos costosas en conjunto a lo largo de toda la serie de operaciones del algoritmo.
4. Complejidad en el peor de los casos : Esta es la complejidad de resolver el problema para la peor entrada de tamaño${\displaystyle n}$.

El orden de menor a mayor costo es: Mejor, promedio (de distribución uniforme discreta ), amortizado, peor.

Por ejemplo, el algoritmo de ordenación determinista quicksort aborda el problema de ordenar una lista de enteros. El peor caso 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 tarda un tiempo O (${\displaystyle n^{2}}$). Si asumimos que todas las permutaciones posibles de la lista de entrada son igualmente probables, el tiempo promedio que se tarda en ordenar es${\displaystyle O(n\log n)}$. El mejor caso se da cuando cada pivote divide la lista por la mitad, necesitando también${\displaystyle O(n\log n)}$tiempo.

Para clasificar el tiempo de cálculo (o recursos similares, como el consumo de espacio), es útil demostrar límites superiores e inferiores para el tiempo máximo requerido por el algoritmo más eficiente para resolver un problema dado. La complejidad de un algoritmo generalmente se considera su complejidad en el peor de los casos, a menos que se especifique lo contrario. El análisis de un algoritmo en particular se enmarca dentro del campo del análisis de algoritmos . Para mostrar un límite superior${\displaystyle T(n)}$En cuanto a la complejidad temporal de un problema, basta con demostrar que existe un algoritmo particular con un tiempo de ejecución máximo${\displaystyle T(n)}$Sin embargo, demostrar cotas inferiores es mucho más difícil, ya que las cotas inferiores hacen una afirmación sobre todos los algoritmos posibles que resuelven un problema dado. La frase "todos los algoritmos posibles" incluye no solo los algoritmos conocidos hoy, sino cualquier algoritmo que pueda descubrirse en el futuro. Para demostrar una cota inferior de${\displaystyle T(n)}$para un problema requiere demostrar que ningún algoritmo puede tener una complejidad temporal menor que${\displaystyle T(n)}$.

Los límites superior e inferior se suelen expresar utilizando la notación O grande , que oculta los factores constantes y los 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${\displaystyle T(n)=7n^{2}+15n+40}$En notación Big O se escribiría:${\displaystyle T(n)\in 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:

• Tipo de problema computacional: Los problemas más comunes son los de decisión. Sin embargo, se pueden definir clases de complejidad basadas en problemas de funciones , problemas de conteo , problemas de optimización , problemas de promesas , etc.
• El modelo de computación: El modelo de computación más comú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ánticas , circuitos monótonos , etc.
• El recurso (o recursos) que se está limitando y el límite: estas dos propiedades se suelen indicar juntas, como "tiempo polinomial", "espacio logarítmico", "profundidad constante", etc.

Algunas clases de complejidad tienen definiciones complicadas que no se ajustan a 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 que puede resolver una máquina de Turing determinista dentro de un tiempo${\displaystyle f(n)}$. (Esta clase de complejidad se conoce como DTIME(${\displaystyle f(n)}$).)

Pero limitando el tiempo de cálculo anterior por alguna función concreta${\displaystyle f(n)}$a menudo produce clases de complejidad que dependen del modelo de máquina elegido. Por ejemplo, el lenguaje${\displaystyle \{xx\mid x{\text{ es cualquier cadena binaria}}\}}$puede resolverse 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 afirma que "las complejidades temporales en cualesquiera dos modelos de computación razonables y generales están relacionadas polinómicamente" ( Goldreich 2008 , Capítulo 1.2) . Esto constituye la base de la clase de complejidad P , que es el conjunto de problemas de decisión resolubles por una máquina de Turing determinista en tiempo polinómico. El conjunto correspondiente de problemas de función 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 definidas de esta manera son las siguientes:

Las clases de espacio logarítmico 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 usando máquinas de Turing probabilísticas ; AC y NC , que se definen usando circuitos booleanos; y BQP y QMA , que se definen usando máquinas de Turing cuánticas. #P es una clase de complejidad importante de problemas de conteo (no de problemas de decisión). Clases como IP y AM se definen usando 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 (por ejemplo) el tiempo de computación define efectivamente un conjunto mayor de problemas. En particular, aunque DTIME(${\displaystyle n}$) está contenido en DTIME(${\displaystyle n^{2}}$Sería interesante saber si la inclusión es estricta. En cuanto a los requisitos de tiempo y espacio, la respuesta a estas preguntas la proporcionan 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 correspondientes. Así, existen pares de clases de complejidad tales que una está incluida adecuadamente en la otra. Una vez deducidas estas inclusiones de conjuntos adecuadas, podemos proceder a formular afirmaciones cuantitativas sobre cuánto 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 ${\displaystyle {\mathsf {DTIME}}{\big (}o(f(n)){\big )}\subsetneq {\mathsf {DTIME}}{\big (}f(n)\cdot \log(f(n)){\big )}}$.

El teorema de la jerarquía espacial establece que ${\displaystyle {\mathsf {DSPACE}}{\big (}o(f(n)){\big )}\subsetneq {\mathsf {DSPACE}}{\big (}f(n){\big )}}$.

Los teoremas de jerarquía temporal y espacial constituyen la base de la mayoría de los resultados de separación de clases de complejidad. Por ejemplo, el teorema de jerarquía temporal nos dice que P está estrictamente contenido en EXPTIME, y el teorema de 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. Captura la noción informal de que un problema es, como máximo, tan difícil como otro. Por ejemplo, si un problema${\displaystyle X}$se puede resolver utilizando un algoritmo para${\displaystyle Y}$,${\displaystyle X}$no es más difícil que${\displaystyle Y}$y decimos que${\displaystyle X}$se reduce a${\displaystyle Y}$. Existen 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 común es la reducción en tiempo polinomial. Esto significa que el proceso de reducción se ejecuta en 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 un algoritmo para multiplicar dos números enteros se puede usar para elevar al cuadrado un número entero. De hecho, esto se puede lograr proporcionando 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 multiplicar.

Esto motiva el concepto de que un problema sea difícil para una clase de complejidad. Un problema${\displaystyle X}$es difícil para una clase de problemas${\displaystyle C}$si cada problema en${\displaystyle C}$puede reducirse a${\displaystyle X}$Por lo tanto, no hay problema en${\displaystyle C}$es más difícil que${\displaystyle X}$, ya que un algoritmo para${\displaystyle X}$nos permite resolver cualquier problema en${\displaystyle 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 suelen usar reducciones en tiempo polinomial. En particular, el conjunto de problemas que son difíciles para NP es el conjunto de problemas NP-difíciles .

Si hay un problema${\displaystyle X}$está en${\displaystyle C}$y difícil para${\displaystyle C}$, entonces${\displaystyle X}$Se dice que está completo para${\displaystyle C}$Esto significa que${\displaystyle X}$es el problema más difícil en${\displaystyle C}$. (Dado que muchos problemas podrían ser igualmente difíciles, se podría decir que${\displaystyle X}$es uno de los problemas más difíciles en${\displaystyle 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 que tienen más probabilidades de no estar en P. Debido a que el problema P = NP no está resuelto, ser capaz de reducir un problema NP-completo conocido,${\displaystyle \Pi _{2}}$, a otro problema,${\displaystyle \Pi _{1}}$, indicaría que no existe una solución conocida de tiempo polinomial para${\displaystyle \Pi _{1}}$Esto se debe a que existe una solución de tiempo polinomial para${\displaystyle \Pi _{1}}$produciría una solución de tiempo polinomial para${\displaystyle \Pi _{2}}$. De manera similar, dado que todos los problemas NP pueden reducirse 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 suele considerar una abstracción matemática que modela aquellas tareas computacionales que admiten un algoritmo eficiente. Esta hipótesis se conoce como la tesis de Cobham-Edmonds . Por otro lado, la clase de complejidad NP contiene muchos problemas que se desearía resolver de manera eficiente, pero para los que no se conoce ningún algoritmo eficiente, como el problema de satisfacibilidad booleana , el problema del camino hamiltoniano y el problema de la 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 pertenece a la clase NP.

La cuestión 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. ^{[ 3 ]} Si la respuesta es afirmativa, 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 operativa , muchos problemas en logística , predicción de la estructura de proteínas en biología , ^{[ 5 ]} y la capacidad de encontrar demostraciones formales de teoremas de matemáticas puras . ^{[ 6 ]} El problema P versus NP es uno de los Problemas del Premio del Milenio propuestos por el Instituto Clay de Matemáticas . Hay un premio de US$1.000.000 por resolver el problema. ^{[ 7 ]}

Ladner demostró que si${\displaystyle {\textsf {P}}\neq {\textsf {NP}}}$entonces existen problemas en${\displaystyle {\textsf {NP}}}$que no están en${\displaystyle {\textsf {P}}}$ni${\displaystyle {\textsf {NP}}}$-completo. ^{[ 4 ]} Estos problemas se denominan problemas NP-intermedios . El problema del isomorfismo de grafos , el problema del logaritmo discreto y el problema de la factorización de enteros son ejemplos de problemas que se consideran NP-intermedios. Son algunos de los pocos problemas NP que no se sabe que estén en${\displaystyle {\textsf {P}}}$o ser${\displaystyle {\textsf {NP}}}$-completo.

El problema del isomorfismo de grafos es el problema computacional de determinar si dos grafos finitos son isomorfos . Un problema importante sin resolver en la teoría de la complejidad es si el problema del isomorfismo de grafos es${\displaystyle {\textsf {P}}}$,${\displaystyle {\textsf {NP}}}$-completo, o NP-intermedio. La respuesta no se conoce, pero se cree que el problema al menos no es NP-completo. ^{[ 8 ]} Si el isomorfismo de grafos 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 de grafos no es NP-completo. El mejor algoritmo para este problema, debido a László Babai y Eugene Luks, tiene un tiempo de ejecución${\displaystyle O(2^{\sqrt {n\log n}})}$para gráficos con${\displaystyle n}$vértices, aunque algunos trabajos recientes de Babai ofrecen algunas perspectivas potencialmente nuevas sobre esto. ^{[ 10 ]}

El problema de factorización de enteros es el problema computacional de determinar la factorización prima de un entero dado. Formulado como un problema de decisión, es el problema de decidir si la entrada tiene un factor primo menor que${\displaystyle 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 la factorización de enteros se encuentra en${\displaystyle {\textsf {NP}}}$y en${\displaystyle {\textsf {co-NP}}}$(e incluso en UP y co-UP ^{[ 11 ]} ). Si el problema es${\displaystyle {\textsf {NP}}}$-completa, la jerarquía de tiempo polinomial colapsará a su primer nivel (es decir,${\displaystyle {\textsf {NP}}}$será igual${\displaystyle {\textsf {co-NP}}}$). El algoritmo más conocido para la factorización de enteros es la criba de cuerpos numéricos general , que requiere tiempo${\displaystyle O(e^{\left({\sqrt[{3}]{\frac {64}{9}}}\right){\sqrt[{3}]{(\log n)}}{\sqrt[{3}]{(\log \log n)^{2}}}})}$^{[ 12 ]} factorizar un número entero impar${\displaystyle n}$Sin embargo, el algoritmo cuántico más conocido para este problema, el algoritmo de Shor , se ejecuta en tiempo polinomial. Desafortunadamente, este hecho no aclara mucho sobre la complejidad del problema en comparación con otras clases de complejidad no cuántica.

Se sospecha que muchas clases de complejidad conocidas son desiguales, pero esto no se ha demostrado. Por ejemplo${\displaystyle {\textsf {P}}\subseteq {\textsf {NP}}\subseteq {\textsf {PP}}\subseteq {\textsf {PSPACE}}}$, pero es posible que${\displaystyle {\textsf {P}}={\textsf {PSPACE}}}$. Si${\displaystyle {\textsf {P}}}$no es igual a${\displaystyle {\textsf {NP}}}$, entonces${\displaystyle {\textsf {P}}}$no es igual a${\displaystyle {\textsf {PSPACE}}}$cualquiera. Dado que existen muchas clases de complejidad conocidas entre${\displaystyle {\textsf {P}}}$y${\displaystyle {\textsf {PSPACE}}}$, como${\displaystyle {\textsf {RP}}}$,${\displaystyle {\textsf {BPP}}}$,${\displaystyle {\textsf {PP}}}$,${\displaystyle {\textsf {BQP}}}$,${\displaystyle {\textsf {MA}}}$,${\displaystyle {\textsf {PH}}}$, etc., es posible que todas estas clases de complejidad se reduzcan a una sola. Demostrar que alguna de estas clases es desigual supondría un gran avance en la teoría de la complejidad.

En la misma línea,${\displaystyle {\textsf {co-NP}}}$es la clase que contiene los problemas complementarios (es decir, problemas con las respuestas sí / no invertidas) de${\displaystyle {\textsf {NP}}}$problemas. Se cree ^{[ 13 ]} que${\displaystyle {\textsf {NP}}}$no es igual a${\displaystyle {\textsf {co-NP}}}$Sin embargo, aún no se ha demostrado. Está claro que si estas dos clases de complejidad no son iguales, entonces${\displaystyle {\textsf {P}}}$no es igual a${\displaystyle {\textsf {NP}}}$, desde${\displaystyle {\textsf {P}}={\textsf {co-P}}}$. Por lo tanto, si${\displaystyle P=NP}$hubiéramos tenido${\displaystyle {\textsf {co-P}}={\textsf {co-NP}}}$De dónde${\displaystyle {\textsf {NP}}={\textsf {P}}={\textsf {co-P}}={\textsf {co-NP}}}$.

De igual modo, se desconoce si${\displaystyle {\textsf {L}}}$(el conjunto de todos los problemas que se pueden resolver en el espacio logarítmico) está estrictamente contenido en${\displaystyle {\textsf {P}}}$o igual a${\displaystyle {\textsf {P}}}$. Nuevamente, existen muchas clases de complejidad entre las dos, como por ejemplo:${\displaystyle {\textsf {NL}}}$y${\displaystyle {\textsf {NC}}}$y se desconoce si son clases distintas o iguales.

Se sospecha que${\displaystyle {\textsf {P}}}$y${\displaystyle {\textsf {BPP}}}$son iguales. Sin embargo, actualmente está abierto si${\displaystyle {\textsf {BPP}}={\textsf {NEXP}}}$.

• Arora, Sanjeev ; Barak, Boaz (2009), Complejidad computacional: un enfoque moderno , Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112 
• Downey, Rod; Fellows, Michael (1999), Complejidad parametrizada , Monografías en Ciencias de la Computación, Berlín, Nueva York: Springer-Verlag, ISBN 9780387948836
• Du, Ding-Zhu; Ko, Ker-I (2000), Teoría de la complejidad computacional , John Wiley & Sons, ISBN 978-0-471-34506-0
• Garey, Michael R.; Johnson , David S. (1979). Computadoras e intratabilidad: una guía a la teoría de la NP-completitud . Serie de libros en ciencias matemáticas (1.ª  ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. MR 0519066 . OCLC 247570676 .  
• Goldreich, Oded (2008), Complejidad computacional: una perspectiva conceptual , Cambridge University Press
• van Leeuwen, Jan , ed. (1990), Manual de informática teórica (vol. A): algoritmos y complejidad , MIT Press, ISBN 978-0-444-88071-0
• Papadimitriou, Christos (1994), Complejidad computacional (1.ª  ed.), Addison Wesley, ISBN 978-0-201-53082-7
• Sipser, Michael (2006), Introducción a la teoría de la computación (2.ª  ed.), EE. UU.: Thomson Course Technology, ISBN 978-0-534-95097-2

• Khalil, Hatem; Ulery, Dana (1976), "Una revisión de los estudios actuales sobre la complejidad de los algoritmos para ecuaciones diferenciales parciales", Actas de la conferencia anual sobre ACM 76 , pp. 197–201 , doi : 10.1145/800191.805573 , ISBN  9781450374897, S2CID 15497394 
• Cook, Stephen (1983), "Una visión general de la complejidad computacional", Communications of the ACM , 26 (6): 400– 408, doi : 10.1145/358141.358144 , ISSN 0001-0782 , S2CID 14323396  
• Fortnow, Lance; Homer, Steven ( 2003), "Una breve historia de la complejidad computacional" (PDF) , Boletín de la EATCS , 80 : 95–133
• Mertens, Stephan (2002), "Complejidad computacional para físicos", Computing in Science & Engineering , 4 (3): 31– 47, arXiv : cond-mat/0012185 , Bibcode : 2002CSE.....4c..31M , doi : 10.1109/5992.998639 , ISSN 1521-9615 , S2CID 633346