Clase de complejidad

En la teoría de la complejidad computacional , una clase de complejidad es un conjunto de problemas computacionales "de complejidad relacionada basada en recursos ". ^{[ 1 ]} Los dos recursos analizados más comúnmente son el tiempo y la memoria .

En general, una clase de complejidad se define en términos de un tipo de problema computacional, un modelo de computación y un recurso limitado como el tiempo o la memoria . En particular, la mayoría de las clases de complejidad consisten en problemas de decisión que se pueden resolver con una máquina de Turing y se diferencian por sus requisitos de tiempo o espacio (memoria). Por ejemplo, la clase P es el conjunto de problemas de decisión que una máquina de Turing determinista puede resolver en tiempo polinomial . Sin embargo, existen muchas clases de complejidad definidas en términos de otros tipos de problemas (por ejemplo, problemas de conteo y problemas de funciones ) y que utilizan otros modelos de computación (por ejemplo, máquinas de Turing probabilísticas , sistemas de prueba interactivos , circuitos booleanos y computadoras cuánticas ).

El estudio de las relaciones entre las clases de complejidad es un área importante de investigación en la informática teórica . A menudo existen jerarquías generales de clases de complejidad; por ejemplo, se sabe que varias clases fundamentales de complejidad temporal y espacial se relacionan entre sí de la siguiente manera:

L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE

Donde ⊆ denota la relación de subconjunto . Sin embargo, muchas relaciones aún se desconocen; por ejemplo, uno de los problemas abiertos más famosos en informática se refiere a si P es igual a NP . Las relaciones entre clases a menudo responden preguntas sobre la naturaleza fundamental de la computación. El problema P versus NP , por ejemplo, está directamente relacionado con preguntas sobre si el no determinismo añade alguna capacidad computacional a las computadoras y si los problemas cuyas soluciones pueden verificarse rápidamente también pueden resolverse rápidamente.

Fondo

Las clases de complejidad son conjuntos de problemas computacionales relacionados . Se definen en términos de la dificultad computacional de resolver los problemas que contienen con respecto a un recurso computacional particular.como el tiempo o la memoria. Más formalmente, la definición de una clase de complejidad consta de tres elementos: un tipo de problema computacional, un modelo de computación y un recurso computacional limitado. En particular, la mayoría de las clases de complejidad consisten en problemas de decisión que pueden ser resueltos por una máquina de Turing con recursos de tiempo o espacio limitados . Por ejemplo, la clase de complejidad P se define como el conjunto de problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en tiempo polinomial .

Problemas computacionales

Intuitivamente, un problema computacional es simplemente una pregunta que puede resolverse mediante un algoritmo . Por ejemplo, "¿es el número natural...? " $n$ ¿ primo ? es un problema computacional. Un problema computacional se representa matemáticamente como el conjunto de respuestas al problema. En el ejemplo de primalidad, el problema (llamémoslo ${\texttt {PRIME}}$ ) está representado por el conjunto de todos los números naturales que son primos: ${\texttt {PRIME}}=\{n\in \mathbb {N} |n{\text{ es primo}}\}$ En la teoría de la computación, estas respuestas se representan como cadenas ; por ejemplo, en el ejemplo de primalidad, los números naturales podrían representarse como cadenas de bits que representan números binarios . Por esta razón, los problemas computacionales a menudo se denominan sinónimos de lenguajes, ya que las cadenas de bits representan lenguajes formales (un concepto tomado de la lingüística ); por ejemplo, decir que ${\texttt {PRIME}}$ El problema está en la clase de complejidad P, lo cual es equivalente a decir que el lenguaje ${\texttt {PRIME}}$ está en P.

Problemas de decisión

Los problemas más comúnmente analizados en la informática teórica son los problemas de decisión , el tipo de problemas que se pueden plantear como preguntas de sí o no . El ejemplo de primalidad anterior, por ejemplo, es un ejemplo de un problema de decisión, ya que se puede representar mediante la pregunta de sí o no "¿es el número natural... ?" $n$ primo ". En términos de la teoría de la computación, un problema de decisión se representa como el conjunto de cadenas de entrada a las que una computadora que ejecuta un algoritmo correcto respondería "sí". En el ejemplo de primalidad, ${\texttt {PRIME}}$ es el conjunto de cadenas que representan números naturales que, al ser introducidos en un ordenador que ejecuta un algoritmo que comprueba correctamente la primalidad , el algoritmo responde "sí, este número es primo". Este formato "sí-no" se suele expresar de forma equivalente como "aceptar-rechazar"; es decir, un algoritmo "acepta" una cadena de entrada si la respuesta al problema de decisión es "sí" y la "rechaza" si la respuesta es "no".

Si bien algunos problemas no pueden expresarse fácilmente como problemas de decisión, no obstante abarcan una amplia gama de problemas computacionales. ^{[ 2 ]} Otros tipos de problemas en términos de los cuales se definen ciertas clases de complejidad incluyen:

Problemas de función (por ejemplo, FP )
Problemas de conteo (por ejemplo, #P )
Problemas de optimización
Problemas de promesas (véase la sección "Otros tipos de problemas")

Modelos computacionales

Para concretar la noción de "computadora", en la informática teórica los problemas se analizan en el contexto de un modelo computacional . Los modelos computacionales precisan las nociones de recursos computacionales como "tiempo" y "memoria". En la teoría de la complejidad computacional , las clases de complejidad se ocupan de los requisitos de recursos inherentes a los problemas y no de los requisitos de recursos que dependen de cómo se construye una computadora física. Por ejemplo, en el mundo real, diferentes computadoras pueden requerir diferentes cantidades de tiempo y memoria para resolver el mismo problema debido a la forma en que han sido diseñadas. Al proporcionar representaciones matemáticas abstractas de las computadoras, los modelos computacionales abstraen las complejidades superfluas del mundo real (como las diferencias en la velocidad del procesador ) que obstaculizan la comprensión de los principios fundamentales.

El modelo computacional más utilizado es la máquina de Turing . Si bien existen otros modelos y muchas clases de complejidad se definen en función de ellos (véase la sección "Otros modelos de computación" ), la máquina de Turing se utiliza para definir la mayoría de las clases de complejidad básicas. Con la máquina de Turing, en lugar de utilizar unidades de tiempo estándar como el segundo (que imposibilitan separar el tiempo de ejecución de la velocidad del hardware físico) y unidades de memoria estándar como los bytes , la noción de tiempo se abstrae como el número de pasos elementales que una máquina de Turing realiza para resolver un problema, y la noción de memoria se abstrae como el número de celdas que se utilizan en la cinta de la máquina. Esto se explica con mayor detalle más adelante.

También es posible utilizar los axiomas de Blum para definir clases de complejidad sin hacer referencia a un modelo computacional concreto , pero este enfoque se utiliza con menos frecuencia en la teoría de la complejidad.

Máquinas de Turing deterministas

Ilustración de una máquina de Turing. La "B" indica el símbolo en blanco.

Una máquina de Turing es un modelo matemático de una máquina de computación general. Es el modelo más utilizado en la teoría de la complejidad, debido en gran parte a que se considera tan potente como cualquier otro modelo de computación y es fácil de analizar matemáticamente. Es importante destacar que se cree que si existe un algoritmo que resuelve un problema particular, también existe una máquina de Turing que resuelve ese mismo problema (esto se conoce como la tesis de Church-Turing ); esto significa que se cree que todo algoritmo puede representarse como una máquina de Turing.

Mecánicamente, una máquina de Turing (MT) manipula símbolos (generalmente restringidos a los bits 0 y 1 para proporcionar una conexión intuitiva con las computadoras reales) contenidos en una tira de cinta infinitamente larga. La MT puede leer y escribir, uno a la vez, utilizando un cabezal de cinta. Su funcionamiento está completamente determinado por un conjunto finito de instrucciones elementales, como "en el estado 42, si el símbolo visto es 0, escribir un 1; si el símbolo visto es 1, cambiar al estado 17; en el estado 17, si el símbolo visto es 0, escribir un 1 y cambiar al estado 6". La máquina de Turing comienza solo con la cadena de entrada en su cinta y deja en blanco el resto. La MT acepta la entrada si entra en un estado de aceptación designado y la rechaza si entra en un estado de rechazo. La máquina de Turing determinista (MTD) es el tipo más básico de máquina de Turing. Utiliza un conjunto fijo de reglas para determinar sus acciones futuras (de ahí su nombre de " determinista ").

Un problema computacional puede definirse entonces en términos de una máquina de Turing como el conjunto de cadenas de entrada que acepta una máquina de Turing en particular. Por ejemplo, el problema de primalidad. ${\texttt {PRIME}}$ El conjunto de cadenas (que representan números naturales) que acepta una máquina de Turing que ejecuta un algoritmo que comprueba correctamente la primalidad , se denomina " reconocer un lenguaje" (recordemos que "problema" y "lenguaje" son prácticamente sinónimos en la teoría de la computabilidad y la complejidad) si acepta todas las entradas que pertenecen a dicho lenguaje, y se dice que decide un lenguaje si, además, rechaza todas las entradas que no pertenecen a él (ciertas entradas pueden provocar que una máquina de Turing se ejecute indefinidamente, por lo que la decidibilidad impone la restricción adicional sobre la reconocibilidad de que la máquina de Turing debe detenerse ante todas las entradas). Una máquina de Turing que "resuelve" un problema generalmente se refiere a una que decide el lenguaje.

Las máquinas de Turing permiten comprender intuitivamente los conceptos de "tiempo" y "espacio". La complejidad temporal de una máquina de Turing con una entrada determinada se define como el número de pasos elementales que realiza para alcanzar un estado de aceptación o rechazo. La complejidad espacial se define como el número de celdas de su cinta que utiliza para alcanzar dichos estados.

Máquinas de Turing no deterministas

La máquina de Turing determinista (MTD) es una variante de la máquina de Turing no determinista (MNT). Intuitivamente, una MNT es simplemente una máquina de Turing convencional con la capacidad adicional de explorar múltiples acciones futuras posibles desde un estado dado y "elegir" una rama que acepte (si alguna acepta). Es decir, mientras que una MTD debe seguir una sola rama de computación, una MNT puede imaginarse como un árbol de computación que se ramifica en múltiples rutas computacionales posibles en cada paso (véase la imagen). Si al menos una rama del árbol se detiene con una condición de "aceptación", la MNT acepta la entrada. De esta manera, una MNT puede considerarse como una máquina que explora simultáneamente todas las posibilidades computacionales en paralelo y selecciona una rama de aceptación. ^{[ 3 ]} Las MNT no pretenden ser modelos físicamente realizables, sino máquinas abstractas teóricamente interesantes que dan lugar a diversas clases de complejidad (que a menudo sí tienen definiciones equivalentes físicamente realizables).

La complejidad temporal de una NTM es el número máximo de pasos que la NTM utiliza en cualquier rama de su cálculo. ^{[ 4 ]} De manera similar, la complejidad espacial de una NTM es el número máximo de celdas que la NTM utiliza en cualquier rama de su cálculo.

Las DTM pueden considerarse un caso especial de las NTM que no aprovechan el poder del no determinismo. Por lo tanto, cualquier cálculo que pueda realizar una DTM también puede ser realizado por una NTM equivalente. Asimismo, es posible simular cualquier NTM utilizando una DTM (la DTM simplemente calculará cada rama computacional posible una por una). En consecuencia, ambas son equivalentes en términos de computabilidad. Sin embargo, simular una NTM con una DTM suele requerir mayor tiempo y/o recursos de memoria; como se verá, la magnitud de esta ralentización para ciertas clases de problemas computacionales es una cuestión importante en la teoría de la complejidad computacional.

límites de recursos

Las clases de complejidad agrupan los problemas computacionales según sus requisitos de recursos. Para ello, los problemas computacionales se diferencian mediante límites superiores en la cantidad máxima de recursos que el algoritmo más eficiente necesita para resolverlos. Más específicamente, las clases de complejidad se ocupan de la tasa de crecimiento de los recursos necesarios para resolver problemas computacionales particulares a medida que aumenta el tamaño de la entrada. Por ejemplo, el tiempo que se tarda en resolver problemas de la clase de complejidad P crece a una tasa polinómica a medida que aumenta el tamaño de la entrada, que es comparativamente pequeña en comparación con los problemas de la clase de complejidad exponencial EXPTIME (o, más precisamente, para problemas en EXPTIME que están fuera de P , ya que ${\mathsf {P}}\subseteq {\mathsf {EXPTIME}}$ ).

Cabe destacar que el estudio de las clases de complejidad tiene como objetivo principal comprender la complejidad inherente necesaria para resolver problemas computacionales. Por lo tanto, los teóricos de la complejidad suelen centrarse en encontrar la clase de complejidad más pequeña a la que pertenece un problema y, en consecuencia, en identificar a qué clase pertenece un problema computacional utilizando el algoritmo más eficiente . Por ejemplo, puede existir un algoritmo que resuelva un problema en tiempo exponencial, pero si el algoritmo más eficiente para resolverlo se ejecuta en tiempo polinomial, entonces la complejidad temporal inherente de ese problema se describe mejor como polinomial.

Límites de tiempo

La complejidad temporal de un algoritmo con respecto al modelo de máquina de Turing es el número de pasos que tarda una máquina de Turing en ejecutar un algoritmo con un tamaño de entrada dado. Formalmente, la complejidad temporal para un algoritmo implementado con una máquina de Turing es el número de pasos que tarda una máquina de Turing en ejecutar un algoritmo con un tamaño de entrada determinado. $M$ se define como la función $t_{M}:\mathbb {N} \to \mathbb {N}$ , dónde $t_{M}(n)$ es el número máximo de pasos que $M$ acepta cualquier entrada de longitud $n$ .

En la teoría de la complejidad computacional, los informáticos teóricos se preocupan menos por los valores de tiempo de ejecución específicos y más por la clase general de funciones a la que pertenece la función de complejidad temporal. Por ejemplo, ¿es la función de complejidad temporal un polinomio ? ¿Una función logarítmica ? ¿Una función exponencial ? ¿O algún otro tipo de función?

límites espaciales

La complejidad espacial de un algoritmo con respecto al modelo de máquina de Turing es el número de celdas en la cinta de la máquina de Turing que se requieren para ejecutar un algoritmo con un tamaño de entrada dado. Formalmente, la complejidad espacial de un algoritmo implementado con una máquina de Turing $M$ se define como la función $s_{M}:\mathbb {N} \to \mathbb {N}$ , dónde $s_{M}(n)$ es el número máximo de celdas que $M$ se utiliza en cualquier entrada de longitud $n$ .

Clases de complejidad básicas

Definiciones básicas

Las clases de complejidad se definen a menudo utilizando conjuntos granulares de clases de complejidad llamadas DTIME y NTIME (para complejidad temporal) y DSPACE y NSPACE (para complejidad espacial). Utilizando la notación de la gran O , se definen de la siguiente manera:

La clase de complejidad temporal ${\mathsf {DTIME}}(t(n))$ es el conjunto de todos los problemas que se deciden por un $O(t(n))$ Máquina de Turing determinista en el tiempo.
La clase de complejidad temporal ${\mathsf {NTIME}}(t(n))$ es el conjunto de todos los problemas que se deciden por un $O(t(n))$ Máquina de Turing no determinista en el tiempo.
La clase de complejidad espacial ${\mathsf {DSPACE}}(s(n))$ es el conjunto de todos los problemas que se deciden por un $O(s(n))$ Máquina de Turing determinista espacial.
La clase de complejidad espacial ${\mathsf {NSPACE}}(s(n))$ es el conjunto de todos los problemas que se deciden por un $O(s(n))$ Máquina de Turing no determinista espacial.

Clases de complejidad temporal

P y NP

P es la clase de problemas que pueden ser resueltos por una máquina de Turing determinista en tiempo polinomial y NP es la clase de problemas que pueden ser resueltos por una máquina de Turing no determinista en tiempo polinomial. O más formalmente,

{\mathsf {P}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})

{\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k})

Se suele decir que P es la clase de problemas que pueden ser resueltos "rápidamente" o "eficientemente" por una computadora determinista, ya que la complejidad temporal de resolver un problema en P aumenta relativamente despacio con el tamaño de la entrada.

Una característica importante de la clase NP es que puede definirse equivalentemente como la clase de problemas cuyas soluciones son verificables por una máquina de Turing determinista en tiempo polinomial. Es decir, un lenguaje pertenece a NP si existe una máquina de Turing determinista de tiempo polinomial, denominada verificador, que toma como entrada una cadena $w$ y una cadena de certificado de tamaño polinomial $c$ y acepta $w$ si $w$ está en el idioma y rechaza $w$ si $w$ no está en el idioma. Intuitivamente, el certificado actúa como prueba de que la entrada $w$ está en el idioma. Formalmente: ^{[ 5 ]}

NP es la clase de lenguajes

L

para la cual existe una máquina de Turing determinista de tiempo polinomial

M

y un polinomio

p

de tal manera que para todos

w\in \{0,1\}^{*}

,

w

está en

L

si y solo si existe alguna

c\in \{0,1\}^{p(|w|)}

de tal manera que

M(w,c)

acepta.

Esta equivalencia entre la definición no determinista y la definición del verificador subraya una conexión fundamental entre el no determinismo y la verificabilidad de la solución. Además, proporciona un método útil para demostrar que un lenguaje pertenece a NP : basta con identificar un certificado adecuado y demostrar que puede verificarse en tiempo polinomial.

El problema P versus NP

Aunque pueda parecer que existe una diferencia obvia entre la clase de problemas que se pueden resolver de manera eficiente y la clase de problemas cuyas soluciones son simplemente verificables de manera eficiente, P y NP están en realidad en el centro de uno de los problemas sin resolver más famosos de la informática: el problema P versus NP . Si bien se sabe que ${\mathsf {P}}\subseteq {\mathsf {NP}}$ (intuitivamente, las máquinas de Turing deterministas son solo una subclase de máquinas de Turing no deterministas que no utilizan su no determinismo; o bajo la definición de verificador, P es la clase de problemas cuyos verificadores de tiempo polinomial solo necesitan recibir la cadena vacía como su certificado), no se sabe si NP es estrictamente mayor que P. Si P = NP , entonces se deduce que el no determinismo no proporciona poder computacional adicional sobre el determinismo con respecto a la capacidad de encontrar rápidamente una solución a un problema; es decir, poder explorar todas las ramas posibles de computación proporciona como máximo una aceleración polinomial sobre poder explorar solo una rama. Además, se deduce que si existe una prueba para una instancia de problema y esa prueba se puede comprobar rápidamente para verificar su corrección (es decir, si el problema está en NP ), entonces también existe un algoritmo que puede construir rápidamente esa prueba (es decir, el problema está en P ). ^{[ 6 ]} Sin embargo, la gran mayoría de los científicos de la computación creen que ${\mathsf {P}}\neq {\mathsf {NP}}$ , ^{[ 7 ]} y la mayoría de los esquemas criptográficos empleados hoy en día se basan en la suposición de que ${\mathsf {P}}\neq {\mathsf {NP}}$ . ^{[ 8 ]}

EXPTIME y NEXPTIME

EXPTIME (a veces abreviado como EXP ) es la clase de problemas de decisión que puede resolver una máquina de Turing determinista en tiempo exponencial, y NEXPTIME (a veces abreviado como NEXP ) es la clase de problemas de decisión que puede resolver una máquina de Turing no determinista en tiempo exponencial. O, más formalmente,

{\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(2^{n^{k}})

{\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})

EXPTIME es un superconjunto estricto de P y NEXPTIME es un superconjunto estricto de NP . Además, se cumple que EXPTIME $\subseteq$ NEXPTIME . No se sabe si esto es correcto, pero si P = NP entonces EXPTIME debe ser igual a NEXPTIME .

Clases de complejidad espacial

L y NL

Aunque es posible definir clases de complejidad temporal logarítmica , estas son clases extremadamente estrechas, ya que los tiempos sublineales ni siquiera permiten que una máquina de Turing lea toda la entrada (porque $\log n<n$ ). ^{[ a ]}^{[ 9 ]} Sin embargo, hay una cantidad significativa de problemas que pueden resolverse en espacio logarítmico. Las definiciones de estas clases requieren una máquina de Turing de dos cintas para que la máquina pueda almacenar toda la entrada (se puede demostrar que en términos de computabilidad la máquina de Turing de dos cintas es equivalente a la máquina de Turing de una sola cinta). ^{[ 10 ]} En el modelo de máquina de Turing de dos cintas, una cinta es la cinta de entrada, que es de solo lectura. La otra es la cinta de trabajo, que permite tanto la lectura como la escritura y es la cinta en la que la máquina de Turing realiza los cálculos. La complejidad espacial de la máquina de Turing se mide como el número de celdas que se utilizan en la cinta de trabajo.

L (a veces alargado a LOGSPACE ) se define entonces como la clase de problemas resolubles en el espacio logarítmico en una máquina de Turing determinista y NL (a veces alargado a NLOGSPACE ) es la clase de problemas resolubles en el espacio logarítmico en una máquina de Turing no determinista. O más formalmente, ^{[ 10 ]}

{\mathsf {L}}={\mathsf {DSPACE}}(\log n)

{\mathsf {NL}}={\mathsf {NSPACE}}(\log n)

Se sabe que ${\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {P}}$ Sin embargo, se desconoce si alguna de estas relaciones es correcta.

PSPACE y NPSPACE

Las clases de complejidad PSPACE y NPSPACE son los análogos espaciales de P y NP . Es decir, PSPACE es la clase de problemas resolubles en el espacio polinomial por una máquina de Turing determinista y NPSPACE es la clase de problemas resolubles en el espacio polinomial por una máquina de Turing no determinista. Más formalmente,

{\mathsf {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})

{\mathsf {NPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})

Aunque no se sabe si P = NP , el teorema de Savitch demostró que PSPACE = NPSPACE . También se sabe que ${\mathsf {P}}\subseteq {\mathsf {PSPACE}}$ Esto se deduce intuitivamente del hecho de que, dado que escribir en una celda de la cinta de una máquina de Turing se define como tomar una unidad de tiempo, una máquina de Turing que opere en tiempo polinomial solo puede escribir en un número polinomial de celdas. Se sospecha que P es estrictamente menor que PSPACE , pero esto no se ha demostrado.

EXPSPACE y NEXPSPACE

Las clases de complejidad EXPSPACE y NEXPSPACE son los análogos espaciales de EXPTIME y NEXPTIME . Es decir, EXPSPACE es la clase de problemas resolubles en el espacio exponencial por una máquina de Turing determinista y NEXPSPACE es la clase de problemas resolubles en el espacio exponencial por una máquina de Turing no determinista. O más formalmente,

{\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})

{\mathsf {NEXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})

El teorema de Savitch demostró que EXPSPACE = NEXPSPACE . Esta clase es extremadamente amplia: se sabe que es un superconjunto estricto de PSPACE , NP y P , y se cree que es un superconjunto estricto de EXPTIME .

Propiedades de las clases de complejidad

Cierre

Las clases de complejidad poseen diversas propiedades de cierre . Por ejemplo, las clases de decisión pueden ser cerradas bajo negación , disyunción , conjunción o incluso bajo todas las operaciones booleanas . Además, también pueden ser cerradas bajo diversos esquemas de cuantificación. P , por ejemplo, es cerrada bajo todas las operaciones booleanas y bajo cuantificación sobre dominios de tamaño polinomial. Las propiedades de cierre pueden ser útiles para separar clases; una posible vía para separar dos clases de complejidad es encontrar alguna propiedad de cierre que posea una clase pero no la otra.

Cada clase X que no es cerrada bajo la negación tiene una clase de complemento co-X , que consiste en los complementos de los lenguajes contenidos en X (es decir, ${\textsf {co-X}}=\{L|{\overline {L}}\in {\mathsf {X}}\}$ ). co-NP , por ejemplo, es una clase importante de complejidad del complemento y se encuentra en el centro del problema sin resolver sobre si co-NP = NP .

Las propiedades de cierre son una de las razones clave por las que muchas clases de complejidad se definen de la manera en que lo hacen. ^{[ 11 ]} Tomemos, por ejemplo, un problema que se puede resolver en $O(n)$ tiempo (es decir, en tiempo lineal) y uno que se puede resolver en, como máximo, $O(n^{1000})$ tiempo. Ambos problemas pertenecen a P , sin embargo, el tiempo de ejecución del segundo crece considerablemente más rápido que el del primero a medida que aumenta el tamaño de la entrada. Uno podría preguntarse si sería mejor definir la clase de problemas "eficientemente resolubles" utilizando algún límite polinómico menor, como $O(n^{3})$ , en lugar de todos los polinomios, lo que permite discrepancias tan grandes. Sin embargo, resulta que el conjunto de todos los polinomios es la clase más pequeña de funciones que contiene las funciones lineales que también es cerrada bajo la suma, la multiplicación y la composición (por ejemplo, $O(n^{3})\circ O(n^{2})=O(n^{6})$ , que es un polinomio pero $O(n^{6})>O(n^{3})$ ). ^{[ 11 ]} Dado que nos gustaría que componer un algoritmo eficiente con otro algoritmo eficiente aún se considerara eficiente, los polinomios son la clase más pequeña que garantiza la composición de "algoritmos eficientes". ^{[ 12 ]} (Nótese que la definición de P también es útil porque, empíricamente, casi todos los problemas en P que son prácticamente útiles tienen de hecho tiempos de ejecución polinomiales de bajo orden, y casi todos los problemas fuera de P que son prácticamente útiles no tienen ningún algoritmo conocido con tiempos de ejecución exponenciales pequeños, es decir, con $O(c^{n})$ tiempos de ejecución donde $c$ es cercano a 1. ^{[ 13 ]} )

Reducciones

Muchas clases de complejidad se definen utilizando el concepto de reducción . Una reducción es una transformación de un problema en otro; es decir, una reducción toma datos de entrada de un problema y los transforma en datos de entrada de otro. Por ejemplo, se puede reducir la suma ordinaria en base 10. $x+y$ suma en base 2 mediante transformación $x$ y $y$ a su notación en base 2 (por ejemplo, 5+7 se convierte en 101+111). Formalmente, un problema $X$ se reduce a un problema $Y$ si existe una función $f$ de tal manera que para cada $x\in \Sigma ^{*}$ , $x\in X$ si y solo si $f(x)\in Y$ .

Generalmente, las reducciones se utilizan para capturar la noción de que un problema es al menos tan difícil como otro problema. Por lo tanto, generalmente estamos interesados en utilizar una reducción de tiempo polinomial, ya que cualquier problema $X$ que se puede reducir eficientemente a otro problema $Y$ no es más difícil que $Y$ Formalmente, un problema $X$ ¿Es reducible en tiempo polinomial a un problema? $Y$ si existe una función computable en tiempo polinomial $p$ de tal manera que para todos $x\in \Sigma ^{*}$ , $x\in X$ si y solo si $p(x)\in Y$ .

Cabe señalar que las reducciones pueden definirse de muchas maneras diferentes. Las reducciones comunes son las reducciones de Cook , las reducciones de Karp y las reducciones de Levin , y pueden variar en función de los límites de los recursos, como las reducciones de tiempo polinomial y las reducciones de espacio logarítmico .

Dureza

Las reducciones motivan 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 puede reducirse en tiempo polinomial a $X$ Por lo 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 con una ralentización máxima polinómica. Es de particular importancia que el conjunto de problemas que son difíciles para NP se denomine conjunto de problemas NP-difíciles .

Lo completo

Si hay un problema $X$ es difícil para C y también está en C , entonces $X$ Se dice que es completo para C. Esto significa que $X$ es el problema más difícil en C (ya que podría haber muchos problemas que son igualmente difíciles, más precisamente $X$ es tan difícil como los problemas más difíciles en C ).

De particular importancia es la clase de problemas NP -completos , los problemas más difíciles en NP . Dado que todos los problemas en NP pueden reducirse en tiempo polinomial a problemas NP -completos, encontrar un problema NP -completo que pueda resolverse en tiempo polinomial significaría que P = NP .

Relaciones entre clases de complejidad

Teorema de Savitch

El teorema de Savitch establece la relación entre los recursos espaciales deterministas y no deterministas. Muestra que si una máquina de Turing no determinista puede resolver un problema utilizando $f(n)$ espacio, entonces una máquina de Turing determinista puede resolver el mismo problema en $f(n)^{2}$ espacio, es decir, en el cuadrado del espacio. Formalmente, el teorema de Savitch establece que para cualquier $f(n)>n$ , ^{[ 14 ]}

{\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right).

Una consecuencia importante del teorema de Savitch es que PSPACE = NPSPACE (ya que el cuadrado de un polinomio sigue siendo un polinomio) y EXPSPACE = NEXPSPACE (ya que el cuadrado de una exponencial sigue siendo una exponencial).

Estas relaciones responden a preguntas fundamentales sobre el poder del no determinismo en comparación con el determinismo. En concreto, el teorema de Savitch demuestra que cualquier problema que una máquina de Turing no determinista pueda resolver en el espacio polinomial, una máquina de Turing determinista también puede resolverlo en el mismo espacio. Del mismo modo, cualquier problema que una máquina de Turing no determinista pueda resolver en el espacio exponencial, una máquina de Turing determinista también puede resolverlo en el mismo espacio.

Teoremas de jerarquía

Por definición de DTIME , se deduce que ${\mathsf {DTIME}}(n^{k_{1}})$ está contenido en ${\mathsf {DTIME}}(n^{k_{2}})$ si $k_{1}\leq k_{2}$ , desde $O(n^{k_{1}})\subseteq O(n^{k_{2}})$ si $k_{1}\leq k_{2}$ Sin embargo, esta definición no indica si la inclusión es estricta. Para los requisitos de tiempo y espacio, las condiciones bajo las cuales la inclusión es estricta vienen dadas 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 correspondientes. Los teoremas de jerarquía permiten realizar afirmaciones cuantitativas sobre cuánto tiempo o espacio adicional se necesita para aumentar el número de problemas que se pueden resolver.

El teorema de la jerarquía temporal implica que

{\mathsf {DTIME}}{\big (}f(n){\big )}\subsetneq {\mathsf {DTIME}}{\big (}f(n)\cdot \log ^{2}(f(n)){\big )}

.

El teorema de la jerarquía espacial implica que

{\mathsf {DSPACE}}{\big (}f(n){\big )}\subsetneq {\mathsf {DSPACE}}{\big (}f(n)\cdot \log(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 establece que P está estrictamente contenido en EXPTIME , y el teorema de jerarquía espacial establece que L está estrictamente contenido en PSPACE .

Otros modelos de computación

Si bien las máquinas de Turing deterministas y no deterministas son los modelos de computación más utilizados, muchas clases de complejidad se definen en términos de otros modelos computacionales. En particular,

Se definen varias clases utilizando máquinas de Turing probabilísticas , incluidas las clases BPP , PP , RP y ZPP.
Se definen varias clases utilizando sistemas de prueba interactivos , incluidas las clases IP , MA y AM.
Varias clases se definen utilizando circuitos booleanos , incluidas las clases P/poly y sus subclases NC y AC.
Se definen varias clases utilizando máquinas de Turing cuánticas , incluidas las clases BQP y QMA.

Estos aspectos se explican con mayor detalle a continuación.

Computación aleatoria

Se definen varias clases de complejidad importantes utilizando la máquina de Turing probabilística , una variante de la máquina de Turing que puede lanzar monedas al azar. Estas clases ayudan a describir mejor la complejidad de los algoritmos aleatorios .

Una máquina de Turing probabilística es similar a una máquina de Turing determinista, excepto que en lugar de seguir una única función de transición (un conjunto de reglas sobre cómo proceder en cada paso del cálculo), selecciona probabilísticamente entre múltiples funciones de transición en cada paso. La definición estándar de una máquina de Turing probabilística especifica dos funciones de transición, de modo que la selección de la función de transición en cada paso se asemeja a un lanzamiento de moneda. La aleatoriedad introducida en cada paso del cálculo introduce la posibilidad de error; es decir, las cadenas que la máquina de Turing debería aceptar pueden ser rechazadas en algunas ocasiones, y las cadenas que debería rechazar pueden ser aceptadas en otras. Como resultado, las clases de complejidad basadas en la máquina de Turing probabilística se definen en gran medida en torno a la cantidad de error permitida. Formalmente, se definen utilizando una probabilidad de error. $\epsilon$ Una máquina de Turing probabilística $M$ Se dice que reconoce un idioma. $L$ con probabilidad de error $\epsilon$ si:

una cuerda $w$ en $L$ implica que ${\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon$
una cuerda $w$ no en $L$ implica que ${\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon$

Clases de complejidad importantes

Las clases fundamentales de complejidad temporal aleatoria son ZPP , RP , co-RP , BPP y PP .

La clase más estricta es ZPP (probabilístico de tiempo polinomial con error cero), la clase de problemas que se pueden resolver en tiempo polinomial mediante una máquina de Turing probabilística con probabilidad de error 0. Intuitivamente, esta es la clase más estricta de problemas probabilísticos porque no exige ningún error .

Una clase ligeramente menos restrictiva es RP (tiempo polinomial aleatorio), que no admite errores para cadenas que no pertenecen al lenguaje, pero sí permite errores acotados para cadenas que sí pertenecen a él. De forma más formal, un lenguaje pertenece a RP si existe una máquina de Turing probabilística de tiempo polinomial. $M$ de tal manera que si una cadena no está en el lenguaje entonces $M$ siempre rechaza y si una cadena está en el lenguaje entonces $M$ acepta con una probabilidad de al menos 1/2. La clase co-RP se define de manera similar, excepto que los roles se invierten: no se permite error para cadenas en el lenguaje, pero sí para cadenas que no están en el lenguaje. En conjunto, las clases RP y co-RP abarcan todos los problemas que pueden ser resueltos por máquinas de Turing probabilísticas con error unilateral .

Al flexibilizar aún más los requisitos de error para permitir errores bilaterales , se obtiene la clase BPP (probabilístico de tiempo polinomial con error acotado), la clase de problemas que una máquina de Turing probabilística puede resolver en tiempo polinomial con una probabilidad de error menor a 1/3 (tanto para cadenas en el lenguaje como para las que no lo están). BPP es la clase de complejidad probabilística más relevante en la práctica: los problemas de BPP tienen algoritmos aleatorios eficientes que se pueden ejecutar rápidamente en ordenadores reales. BPP también está en el centro del importante problema sin resolver en informática sobre si P=BPP , lo que, de ser cierto, significaría que la aleatoriedad no aumenta la potencia computacional de los ordenadores; es decir, cualquier máquina de Turing probabilística podría simularse con una máquina de Turing determinista con una ralentización máxima polinomial.

La clase más amplia de problemas probabilísticos que se pueden resolver de manera eficiente es PP (tiempo polinomial probabilístico), el conjunto de lenguajes que puede resolver una máquina de Turing probabilística en tiempo polinomial con una probabilidad de error menor a 1/2 para todas las cadenas.

ZPP , RP y co-RP son todos subconjuntos de BPP , que a su vez es un subconjunto de PP . La razón de esto es intuitiva: las clases que permiten error cero y solo error unilateral están todas contenidas dentro de la clase que permite error bilateral, y PP simplemente relaja la probabilidad de error de BPP . ZPP se relaciona con RP y co-RP de la siguiente manera: ${\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}$ Es decir, ZPP consiste precisamente en aquellos problemas que están tanto en RP como en co-RP . Intuitivamente, esto se deduce del hecho de que RP y co-RP solo permiten errores unilaterales: co-RP no permite errores para cadenas del lenguaje y RP no permite errores para cadenas que no están en el lenguaje. Por lo tanto, si un problema está tanto en RP como en co-RP , entonces no debe haber ningún error para cadenas que estén y no estén en el lenguaje (es decir, ningún error en absoluto), que es precisamente la definición de ZPP .

Las clases importantes de complejidad espacial aleatoria incluyen BPL , RL y RLP .

Sistemas de prueba interactivos

Se definen varias clases de complejidad utilizando sistemas de prueba interactivos . Las pruebas interactivas generalizan la definición de prueba de la clase de complejidad NP y proporcionan información valiosa sobre criptografía , algoritmos de aproximación y verificación formal .

Los sistemas de prueba interactivos son máquinas abstractas que modelan la computación como el intercambio de mensajes entre dos partes: un probador $P$ y un verificador $V$ Las partes interactúan intercambiando mensajes, y el sistema acepta una cadena de entrada si el verificador decide aceptarla basándose en los mensajes que ha recibido del probador. $P$ El sistema de prueba tiene una capacidad computacional ilimitada, mientras que el verificador tiene una capacidad computacional limitada (la definición estándar de los sistemas de prueba interactivos define al verificador como limitado en tiempo polinomial). Sin embargo, el probador no es confiable (esto impide que el sistema de prueba reconozca trivialmente todos los lenguajes al hacer que el probador, con capacidad computacional ilimitada, determine si una cadena pertenece a un lenguaje y luego envíe un "SÍ" o "NO" confiable al verificador), por lo que el verificador debe realizar un "interrogatorio" del probador haciéndole sucesivas rondas de preguntas, aceptando solo si desarrolla un alto grado de confianza en que la cadena pertenece al lenguaje. ^{[ 15 ]}

Clases de complejidad importantes

La clase NP es un sistema de prueba simple en el que el verificador se limita a ser una máquina de Turing determinista de tiempo polinomial y el procedimiento se limita a una ronda (es decir, el probador envía solo una única prueba completa —generalmente denominada certificado— al verificador). Dicho de otro modo, en la definición de la clase NP (el conjunto de problemas de decisión para los cuales las instancias del problema, cuando la respuesta es "SÍ", tienen pruebas verificables en tiempo polinomial por una máquina de Turing determinista) se encuentra un sistema de prueba en el que la prueba es construida por un probador no mencionado y la máquina de Turing determinista es el verificador. Por esta razón, NP también puede denominarse dIP (prueba interactiva determinista), aunque rara vez se hace referencia a ella con ese nombre.

Resulta que NP captura todo el potencial de los sistemas de prueba interactivos con verificadores deterministas (de tiempo polinomial) porque se puede demostrar que para cualquier sistema de prueba con un verificador determinista nunca es necesario más de una ronda de mensajes entre el probador y el verificador. Los sistemas de prueba interactivos que proporcionan mayor potencia computacional que las clases de complejidad estándar requieren, por lo tanto, verificadores probabilísticos , lo que significa que las preguntas del verificador al probador se calculan utilizando algoritmos probabilísticos . Como se señaló en la sección anterior sobre computación aleatoria , los algoritmos probabilísticos introducen errores en el sistema, por lo que las clases de complejidad basadas en sistemas de prueba probabilísticos se definen en términos de una probabilidad de error. $\epsilon$ .

La clase de complejidad más general que surge de esta caracterización es la clase IP (tiempo polinomial interactivo), que es la clase de todos los problemas resolubles por un sistema de prueba interactivo. $(P,V)$ , dónde $V$ es probabilístico en tiempo polinomial y el sistema de prueba satisface dos propiedades: para un lenguaje $L\in {\mathsf {IP}}$

(Completitud) una cadena $w$ en $L$ implica $\Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\geq {\tfrac {2}{3}}$
(Sonido) una cuerda $w$ no en $L$ implica $\Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\leq {\tfrac {1}{3}}$

Una característica importante de IP es que es igual a PSPACE . En otras palabras, cualquier problema que pueda ser resuelto por un sistema de prueba interactivo de tiempo polinomial también puede ser resuelto por una máquina de Turing determinista con recursos de espacio polinomial, y viceversa.

Una modificación del protocolo para IP produce otra clase de complejidad importante: AM (protocolo Arthur-Merlin). En la definición de sistemas de prueba interactivos utilizados por IP , el probador no podía ver las monedas utilizadas por el verificador en su cálculo probabilístico; solo podía ver los mensajes que el verificador producía con esas monedas. Por esta razón, las monedas se denominan monedas aleatorias privadas . El sistema de prueba interactivo puede restringirse de modo que las monedas utilizadas por el verificador sean monedas aleatorias públicas ; es decir, el probador puede ver las monedas. Formalmente, AM se define como la clase de lenguajes con una prueba interactiva en la que el verificador envía una cadena aleatoria al probador, el probador responde con un mensaje, y el verificador lo acepta o lo rechaza aplicando una función determinista de tiempo polinomial al mensaje del probador. AM puede generalizarse a AM [ k ], donde k es el número de mensajes intercambiados (por lo que en la forma generalizada, el AM estándar definido anteriormente es AM [2]). Sin embargo, es cierto que para todos $k\geq 2$ , AM [ k ]= AM [2]. También es cierto que ${\mathsf {AM}}[k]\subseteq {\mathsf {IP}}[k]$ .

Otras clases de complejidad definidas mediante sistemas de prueba interactivos incluyen MIP (tiempo polinomial interactivo con múltiples probadores) y QIP (tiempo polinomial interactivo cuántico).

Circuitos booleanos

{\displaystyle f_{C}(x_{1},x_{2},x_{3})=\neg (x_{1}\wedge x_{2})\wedge ((x_{2}\wedge x_{3})\vee \neg x_{3})} — Ejemplo de circuito booleano que calcula la función booleana $f_{C}(x_{1},x_{2},x_{3})=\neg (x_{1}\wedge x_{2})\wedge ((x_{2}\wedge x_{3})\vee \neg x_{3})$ , con entrada de ejemplo $x_{1}=0$ , $x_{2}=1$ , y $x_{3}=0$ . El $\wedge$ Los nodos son puertas AND , el $\vee$ Los nodos son puertas OR y el $\neg$ Los nodos NO son puertas .

Un modelo de computación alternativo a la máquina de Turing es el circuito booleano , un modelo simplificado de los circuitos digitales utilizados en las computadoras modernas . Este modelo no solo proporciona una conexión intuitiva entre la computación teórica y la práctica, sino que también es un modelo natural para la computación no uniforme (computación en la que diferentes tamaños de entrada dentro del mismo problema utilizan diferentes algoritmos).

Formalmente, un circuito booleano $C$ Es un grafo dirigido acíclico en el que las aristas representan cables (que transportan los valores de bit 0 y 1), los bits de entrada están representados por vértices fuente (vértices sin aristas entrantes) y todos los vértices que no son fuente representan compuertas lógicas (generalmente las compuertas AND , OR y NOT ). Una compuerta lógica se designa como compuerta de salida y representa el final del cálculo. El comportamiento de entrada/salida de un circuito $C$ con $n$ Las variables de entrada están representadas por la función booleana. $f_{C}:\{0,1\}^{n}\to \{0,1\}$ ; por ejemplo, en los bits de entrada $x_{1},x_{2},...,x_{n}$ , el bit de salida $b$ del circuito se representa matemáticamente como $b=f_{C}(x_{1},x_{2},...,x_{n})$ El circuito $C$ Se dice que calcula la función booleana $f_{C}$ .

Cualquier circuito particular tiene un número fijo de vértices de entrada, por lo que solo puede operar con entradas de ese tamaño. Sin embargo, los lenguajes (las representaciones formales de problemas de decisión ) contienen cadenas de longitudes diferentes, por lo que no pueden ser representados completamente por un solo circuito (esto contrasta con el modelo de máquina de Turing, en el que un lenguaje se describe completamente mediante una única máquina de Turing que puede operar con cualquier tamaño de entrada). Por lo tanto, un lenguaje se representa mediante una familia de circuitos . Una familia de circuitos es una lista infinita de circuitos. $(C_{0},C_{1},C_{2},...)$ , dónde $C_{n}$ es un circuito con $n$ variables de entrada. Se dice que una familia de circuitos decide un lenguaje. $L$ si, para cada cadena $w$ , $w$ está en el idioma $L$ si y solo si $C_{n}(w)=1$ , dónde $n$ es la longitud de $w$ En otras palabras, una cadena $w$ de tamaño $n$ está en el lenguaje representado por la familia de circuitos $(C_{0},C_{1},C_{2},...)$ si el circuito $C_{n}$ (el circuito con el mismo número de vértices de entrada que el número de bits en $w$ ) se evalúa a 1 cuando $w$ es su entrada.

Mientras que las clases de complejidad definidas mediante máquinas de Turing se describen en términos de complejidad temporal , las clases de complejidad de circuitos se definen en términos de tamaño del circuito: el número de vértices en el circuito. La complejidad de tamaño de una familia de circuitos $(C_{0},C_{1},C_{2},...)$ es la función $f:\mathbb {N} \to \mathbb {N}$ , dónde $f(n)$ es el tamaño del circuito de $C_{n}$ . Las clases de funciones familiares se derivan naturalmente de esto; por ejemplo, una familia de circuitos de tamaño polinomial es aquella tal que la función $f$ es un polinomio .

Clases de complejidad importantes

La clase de complejidad P/poly es el conjunto de lenguajes que son decidibles por familias de circuitos de tamaño polinomial. Resulta que existe una conexión natural entre la complejidad de circuitos y la complejidad temporal. Intuitivamente, un lenguaje con una complejidad temporal pequeña (es decir, que requiere relativamente pocas operaciones secuenciales en una máquina de Turing) también tiene una complejidad de circuitos pequeña (es decir, que requiere relativamente pocas operaciones booleanas). Formalmente, se puede demostrar que si un lenguaje está en ${\mathsf {DTIME}}(t(n))$ , dónde $t$ es una función $t:\mathbb {N} \to \mathbb {N}$ entonces tiene complejidad de circuito $O(t^{2}(n))$ . ^{[ 16 ]} De este hecho se deduce directamente que ${\mathsf {\color {Blue}P}}\subset {\textsf {P/poly}}$ En otras palabras, cualquier problema que pueda resolverse en tiempo polinomial mediante una máquina de Turing determinista también puede resolverse mediante una familia de circuitos de tamaño polinomial. Además, la inclusión es propia, es decir, ${\textsf {P}}\subsetneq {\textsf {P/poly}}$ (por ejemplo, hay algunos problemas indecidibles que están en P/poly ).

P/poly tiene una serie de propiedades que lo hacen muy útil en el estudio de las relaciones entre clases de complejidad. En particular, es útil para investigar problemas relacionados con P versus NP . Por ejemplo, si hay algún lenguaje en NP que no esté en P/poly , entonces ${\mathsf {P}}\neq {\mathsf {NP}}$ . ^{[ 17 ]} P/poly también es útil para investigar propiedades de la jerarquía polinómica . Por ejemplo, si NP ⊆ P/poly , entonces PH se reduce a $\Sigma _{2}^{\mathsf {P}}$ Una descripción completa de las relaciones entre P/poly y otras clases de complejidad está disponible en " Importancia de P/poly ". P/poly también es útil en el estudio general de las propiedades de las máquinas de Turing , ya que la clase puede definirse equivalentemente como la clase de lenguajes reconocidos por una máquina de Turing de tiempo polinomial con una función de consejo acotada polinomialmente .

Dos subclases de P/poly que poseen propiedades interesantes por derecho propio son NC y AC . Estas clases se definen no solo en términos del tamaño de su circuito, sino también en términos de su profundidad . La profundidad de un circuito es la longitud del camino dirigido más largo desde un nodo de entrada al nodo de salida. La clase NC es el conjunto de lenguajes que pueden resolverse mediante familias de circuitos que están restringidas no solo a tener un tamaño polinomial, sino también a tener una profundidad polilogarítmica. La clase AC se define de manera similar a NC , sin embargo, se permite que las compuertas tengan un fan-in ilimitado (es decir, las compuertas AND y OR pueden aplicarse a más de dos bits). NC es una clase notable porque puede definirse equivalentemente como la clase de lenguajes que poseen algoritmos paralelos eficientes .

Computación cuántica

Las clases BQP (tiempo polinomial cuántico con error acotado) y QMA (Quantum Merlin Arthur), de vital importancia en la ciencia de la información cuántica , se definen utilizando máquinas de Turing cuánticas . Su relación es análoga a la relación entre P y NP , y también a la relación entre MA y BPP . Actualmente se sabe que:

{\mathsf {P\subseteq BPP\subseteq BQP\subseteq AWPP\subseteq PP\subseteq PSPACE\subseteq EXP}}

y:

{\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {MA}}\subseteq {\mathsf {QCMA}}\subseteq {\mathsf {QMA}}\subseteq {\mathsf {PP}}\subseteq {\mathsf {PSPACE}}

Aunque la relación entre BQP y NP sigue siendo desconocida.

Otros tipos de problemas

Si bien la mayoría de las clases de complejidad estudiadas por los informáticos son conjuntos de problemas de decisión , también existen clases de complejidad definidas en términos de otros tipos de problemas. En particular, hay clases de complejidad que consisten en problemas de conteo , problemas de funciones y problemas de promesas . Estas se explican con mayor detalle a continuación.

Problemas de conteo

Un problema de conteo no solo pregunta si existe una solución (como en un problema de decisión ), sino cuántas soluciones existen. ^{[ 18 ]} Por ejemplo, el problema de decisión ${\texttt {CYCLE}}$ pregunta si un gráfico en particular $G$ tiene un ciclo simple (la respuesta es un simple sí/no); el problema de conteo correspondiente $\#{\texttt {CYCLE}}$ (pronunciado "sharp cycle") pregunta cuántos ciclos simples $G$ tiene. ^{[ 19 ]} La salida de un problema de conteo es, por lo tanto, un número, en contraste con la salida de un problema de decisión, que es un simple sí/no (o aceptar/rechazar, 0/1 u otro esquema equivalente). ^{[ 20 ]}

Así, mientras que los problemas de decisión se representan matemáticamente como lenguajes formales , los problemas de conteo se representan matemáticamente como funciones : un problema de conteo se formaliza como la función $f:\{0,1\}^{*}\to \mathbb {N}$ de tal manera que para cada entrada $w\in \{0,1\}^{*}$ , $f(w)$ es el número de soluciones. Por ejemplo, en el $\#{\texttt {CYCLE}}$ problema, la entrada es un gráfico $G\in \{0,1\}^{*}$ (un gráfico representado como una cadena de bits ) y $f(G)$ es el número de ciclos simples en $G$ .

Los problemas de conteo surgen en varios campos, incluyendo la estimación estadística , la física estadística , el diseño de redes y la economía . ^{[ 21 ]}

Clases de complejidad importantes

#P (pronunciado "P fuerte") es una clase importante de problemas de conteo que puede considerarse como la versión de conteo de NP . ^{[ 22 ]} La conexión con NP surge del hecho de que el número de soluciones a un problema es igual al número de ramas de aceptación en el árbol de computación de una máquina de Turing no determinista . #P se define formalmente de la siguiente manera:

#P es el conjunto de todas las funciones

f:\{0,1\}^{*}\to \mathbb {N}

de tal manera que exista una máquina de Turing no determinista de tiempo polinomial

M

de tal manera que para todos

w\in \{0,1\}^{*}

,

f(w)

es igual al número de sucursales que aceptan

M

árbol de computación de

w

. ^{[ 22 ]}

Y así como NP puede definirse tanto en términos de no determinismo como en términos de un verificador (es decir, como un sistema de prueba interactivo ), también #P puede definirse equivalentemente en términos de un verificador. Recordemos que un problema de decisión está en NP si existe un certificado verificable en tiempo polinomial para una instancia de problema dada; es decir, NP pregunta si existe una prueba de pertenencia (un certificado) para la entrada que pueda verificarse en tiempo polinomial. La clase #P pregunta cuántos de estos certificados existen. ^{[ 22 ]} En este contexto, #P se define de la siguiente manera:

#P es el conjunto de funciones

f:\{0,1\}^{*}\to \mathbb {N}

tal que existe un polinomio

p:\mathbb {N} \to \mathbb {N}

y una máquina de Turing de tiempo polinomial

V

(el verificador), de tal manera que para cada

w\in \{0,1\}^{*}

,

f(w)={\Big |}{\big \{}c\in \{0,1\}^{p(|w|)}:V(w,c)=1{\big \}}{\Big |}

. ^{[ 23 ]} En otras palabras,

f(w)

es igual al tamaño del conjunto que contiene todos los certificados de tamaño polinomial para

w

.

Problemas de funcionamiento

Los problemas de conteo son un subconjunto de una clase más amplia de problemas llamados problemas de funciones . Un problema de funciones es un tipo de problema en el que los valores de una función $f:A\to B$ se calculan. Formalmente, un problema de función $f$ se define como una relación $R$ sobre cadenas de un alfabeto arbitrario $\Sigma$ :

R\subseteq \Sigma ^{*}\times \Sigma ^{*}

Un algoritmo resuelve $f$ si para cada entrada $x$ de tal manera que exista una $y$ satisfactorio $(x,y)\in R$ , el algoritmo produce uno de esos $y$ . Esta es solo otra forma de decir que $f$ es una función y el algoritmo la resuelve $f(x)$ a pesar de $x\in \Sigma ^{*}$ .

Clases de complejidad importantes

Una clase importante de complejidad de funciones es FP , la clase de funciones eficientemente resolubles. ^{[ 23 ]} Más específicamente, FP es el conjunto de problemas de funciones que pueden ser resueltos por una máquina de Turing determinista en tiempo polinomial . ^{[ 23 ]} FP puede considerarse como el equivalente de P en el ámbito de los problemas de funciones . Es importante destacar que FP proporciona información sobre los problemas de conteo y sobre P frente a NP . Si #P = FP , entonces las funciones que determinan el número de certificados para problemas en NP son eficientemente resolubles. Y dado que calcular el número de certificados es al menos tan difícil como determinar si existe un certificado, debe seguirse que si #P = FP, entonces P = NP (no se sabe si esto se cumple a la inversa, es decir, si P = NP implica #P = FP ). ^{[ 23 ]}

Así como FP es el problema de función equivalente de P , FNP es el problema de función equivalente de NP . Es importante destacar que FP = FNP si y solo si P = NP . ^{[ 24 ]}

Problemas de promesas

Los problemas de promesa son una generalización de los problemas de decisión en los que se garantiza ("se promete") que la entrada a un problema provenga de un subconjunto particular de todas las entradas posibles. Recordemos que con un problema de decisión $L\subseteq \{0,1\}^{*}$ , un algoritmo $M$ para $L$ debe actuar (correctamente) en cada $w\in \{0,1\}^{*}$ . Un problema de promesas flexibiliza el requisito de entrada en $M$ al restringir la entrada a algún subconjunto de $\{0,1\}^{*}$ .

Específicamente, un problema de promesa se define como un par de conjuntos que no se intersecan. $(\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})$ , donde: ^{[ 25 ]}

$\Pi _{\text{ACCEPT}}\subseteq \{0,1\}^{*}$ es el conjunto de todas las entradas que se aceptan.
$\Pi _{\text{REJECT}}\subseteq \{0,1\}^{*}$ es el conjunto de todas las entradas que son rechazadas.

La entrada a un algoritmo $M$ para un problema de promesa $(\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})$ es así $\Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}$ , que se llama promesa . Cadenas en $\Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}$ Se dice que satisfacen la promesa . ^{[ 25 ]} Por definición, $\Pi _{\text{ACCEPT}}$ y $\Pi _{\text{REJECT}}$ debe ser disjunto, es decir $\Pi _{\text{ACCEPT}}\cap \Pi _{\text{REJECT}}=\emptyset$ .

Dentro de esta formulación, se puede ver que los problemas de decisión son simplemente el subconjunto de problemas de promesa con la promesa trivial. $\Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}=\{0,1\}^{*}$ . Con los problemas de decisión, es más sencillo definir el problema simplemente como solo $\Pi _{\text{ACCEPT}}$ (con $\Pi _{\text{REJECT}}$ implícitamente ser $\{0,1\}^{*}/\Pi _{\text{ACCEPT}}$ ), que a lo largo de esta página se denota $L$ para enfatizar que $\Pi _{\text{ACCEPT}}=L$ es un lenguaje formal .

Los problemas de promesas permiten una formulación más natural de muchos problemas computacionales. Por ejemplo, un problema computacional podría ser algo como "dado un grafo planar , determinar si o no..." ^{[ 26 ]} Esto se suele plantear como un problema de decisión, donde se supone que existe algún esquema de traducción que toma cada cadena $s\in \{0,1\}^{*}$ a un grafo planar. Sin embargo, es más sencillo definirlo como un problema de promesa en el que se promete que la entrada será un grafo planar.

Relación con las clases de complejidad

Los problemas de promesa proporcionan una definición alternativa para las clases de complejidad estándar de los problemas de decisión. P , por ejemplo, puede definirse como un problema de promesa: ^{[ 27 ]}

P es la clase de problemas de promesa que se pueden resolver en tiempo polinomial determinista. Es decir, el problema de promesa

(\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})

está en P si existe un algoritmo de tiempo polinomial

M

de tal manera que:

Por cada $x\in \Pi _{\text{ACCEPT}},M(x)=1$
Para siempre $x\in \Pi _{\text{REJECT}},M(x)=0$

Las clases de problemas de decisión —es decir, las clases de problemas definidos como lenguajes formales— se traducen así naturalmente a problemas de promesas, donde un lenguaje $L$ en la clase es simplemente $L=\Pi _{\text{ACCEPT}}$ y $\Pi _{\text{REJECT}}$ es implícitamente $\{0,1\}^{*}/\Pi _{\text{ACCEPT}}$ .

Formular muchas clases de complejidad básicas, como P, como problemas de promesa aporta poca información adicional sobre su naturaleza. Sin embargo, existen algunas clases de complejidad para las que formularlas como problemas de promesa ha resultado útil para los informáticos. Los problemas de promesa, por ejemplo, han desempeñado un papel fundamental en el estudio del conocimiento cero estadístico ( SZK ). ^{[ 28 ]}

Resumen de las relaciones entre las clases de complejidad

La siguiente tabla muestra algunas de las clases de problemas que se consideran en la teoría de la complejidad. Si la clase X es un subconjunto estricto de Y , entonces X se muestra debajo de Y con una línea oscura que las conecta. Si X es un subconjunto, pero se desconoce si son conjuntos iguales, entonces la línea es más clara y punteada. Técnicamente, la división en decidibles e indecidibles pertenece más al estudio de la teoría de la computabilidad , pero es útil para contextualizar las clases de complejidad.

Véase también

Lista de clases de complejidad

Notas

↑ Mientras que un tiempo de ejecución logarítmico de $c\log n$ , es decir $\log n$ multiplicado por una constante $c$ , permite que una máquina de Turing lea entradas de tamaño $n<c\log n$ , invariablemente llegará un punto en el que $n>c\log n$ .

Referencias

↑ Johnson (1990) .
^ Arora y Barak 2009 , pág. 28.
↑ Sipser 2006 , pág. 48, 150.
↑ Sipser 2006 , pág. 255.
↑ Aaronson 2017 , pág. 12.
↑ Aaronson 2017 , pág. 3.
↑ Gasarch 2019 .
↑ Aaronson 2017 , pág. 4.
↑ Sipser 2006 , pág. 320.
1 2 Sipser 2006 , pág. 321.
1 2 Aaronson 2017 , pág. 7.
↑ Aaronson 2017 , pág. 5.
↑ Aaronson 2017 , pág. 6.
↑ Lee 2014 .
^ Arora y Barak 2009 , pág. 144.
↑ Sipser 2006 , pág. 355.
^ Arora y Barak 2009 , pág. 286.
↑ Fortnow 1997 .
↑ Arora 2003 .
^ Arora y Barak 2009 , pág. 342.
^ Arora y Barak 2009 , pág. 341–342.
1 2 3 Barak 2006 .
^ Arora y Barak 2009 , pág . 344.
↑ Rich 2008 , pág. 689 (510 en el PDF proporcionado).
1 2 Watrous 2006 , pág. 1.
↑ Goldreich 2006 , pág. 255 (2–3 en el pdf proporcionado).
↑ Goldreich 2006 , pág. 257 (4 en el pdf proporcionado).
↑ Goldreich 2006 , pág. 266 (11-12 en el pdf proporcionado).

Bibliografía

Aaronson, Scott (8 de enero de 2017). "P=?NP" . Coloquio electrónico sobre complejidad computacional . Instituto Weizmann de Ciencias. Archivado del original el 17 de junio de 2020.
Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional: un enfoque moderno . Cambridge University Press. Borrador . Archivado del original el 23 de febrero de 2022. ISBN 978-0-521-42426-4.
Arora, Sanjeev (Primavera de 2003). "Clases de complejidad relacionadas con el conteo" . Ciencias de la Computación 522: Teoría de la Complejidad Computacional . Universidad de Princeton. Archivado del original el 21 de mayo de 2022.
Barak, Boaz (Primavera de 2006). "Complejidad del conteo" (PDF) . Ciencias de la Computación 522: Complejidad Computacional . Universidad de Princeton . Archivado del original el 3 de abril de 2021.
Fortnow, Lance (1997). «Counting Complexity» (PDF) . En Hemaspaandra, Lane A.; Selman, Alan L. (eds.). Complexity Theory Retrospective II . Springer. pp. 81–106 . ISBN 9780387949734Archivado del original (PDF) el 18 de junio de 2022.
Gasarch, William I. (2019). "Columna invitada: La tercera encuesta P =? NP" (PDF) . Universidad de Maryland . Archivado (PDF) del original el 2 de noviembre de 2021.
Goldreich, Oded (2006). "Sobre los problemas de promesas: una revisión" (PDF) . En Goldreich, Oded; Rosenberg, Arnold L.; Selman, Alen L. (eds.). Informática teórica. Lecture Notes in Computer Science, vol. 3895 (PDF) . Vol. 3895. Springer. pp. 254–290 . doi : 10.1007/11685654_12 . ISBN 978-3-540-32881-0Archivado (PDF) del original el 6 de mayo de 2021 .
Johnson, David S. (1990). «Un catálogo de clases de complejidad». Algoritmos y complejidad . Manual de informática teórica. Elsevier. págs. 67–161 . doi : 10.1016/b978-0-444-88071-0.50007-2 . ISBN 978-0-444-88071-0.
Lee, James R. (22 de mayo de 2014). "Clase 16" (PDF) . CSE431: Introducción a la teoría de la computación . Universidad de Washington . Archivado (PDF) del original el 29 de noviembre de 2021. Recuperado el 5 de octubre de 2022 .
Rich, Elaine (2008). Autómatas, computabilidad y complejidad: teoría y aplicaciones (PDF) . Prentice Hall . ISBN 978-0132288064Archivado (PDF) del original el 21 de enero de 2022 .
Sipser, Michael (2006). Introducción a la teoría de la computación (PDF) (2.ª ed.). EE. UU.: Thomson Course Technology. ISBN 0-534-95097-3Archivado del original (PDF) el 7 de febrero de 2022.
Watrous, John (11 de abril de 2006). "Conferencia 22: Complejidad computacional cuántica" (PDF) . Universidad de Waterloo . Archivado (PDF) del original el 18 de junio de 2022.

Lecturas adicionales

El Zoológico de la Complejidad Archivado el 27/08/2019 en la Wayback Machine : Una enorme lista de clases de complejidad, una referencia para expertos.
Neil Immerman . "Teoría de la complejidad computacional" . Archivado del original el 16 de abril de 2016.Incluye un diagrama que muestra la jerarquía de las clases de complejidad y cómo se relacionan entre sí.
Michael Garey y David S. Johnson : Computadoras e intratabilidad: una guía a la teoría de la NP-completitud. Nueva York: WH Freeman & Co., 1979. La obra de referencia estándar sobre problemas NP-completos, una categoría importante de problemas cuyas soluciones parecen requerir un tiempo de cálculo excesivamente largo.

[9] Mientras que un tiempo de ejecución logarítmico de $c\log n$ , es decir $\log n$ multiplicado por una constante $c$ , permite que una máquina de Turing lea entradas de tamaño $n<c\log n$ , invariablemente llegará un punto en el que $n>c\log n$ .

[FOOTNOTEJohnson1990-1] Johnson (1990) .

[FOOTNOTEAroraBarak200928-2] Arora y Barak 2009 , pág. 28.

[FOOTNOTESipser200648,_150-3] Sipser 2006 , pág. 48, 150.

[FOOTNOTESipser2006255-4] Sipser 2006 , pág. 255.

[FOOTNOTEAaronson201712-5] Aaronson 2017 , pág. 12.

[FOOTNOTEAaronson20173-6] Aaronson 2017 , pág. 3.

[FOOTNOTEGasarch2019-7] Gasarch 2019 .

[FOOTNOTEAaronson20174-8] Aaronson 2017 , pág. 4.

[FOOTNOTESipser2006320-10] Sipser 2006 , pág. 320.

[FOOTNOTESipser2006321-11] 1 2 Sipser 2006 , pág. 321.

[FOOTNOTEAaronson20177-12] 1 2 Aaronson 2017 , pág. 7.

[FOOTNOTEAaronson20175-13] Aaronson 2017 , pág. 5.

[FOOTNOTEAaronson20176-14] Aaronson 2017 , pág. 6.

[FOOTNOTELee2014-15] Lee 2014 .

[FOOTNOTEAroraBarak2009144-16] Arora y Barak 2009 , pág. 144.

[FOOTNOTESipser2006355-17] Sipser 2006 , pág. 355.

[FOOTNOTEAroraBarak2009286-18] Arora y Barak 2009 , pág. 286.

[FOOTNOTEFortnow1997-19] Fortnow 1997 .

[FOOTNOTEArora2003-20] Arora 2003 .

[FOOTNOTEAroraBarak2009342-21] Arora y Barak 2009 , pág. 342.

[FOOTNOTEAroraBarak2009341–342-22] Arora y Barak 2009 , pág. 341–342.

[FOOTNOTEBarak2006-23] 1 2 3 Barak 2006 .

[FOOTNOTEAroraBarak2009344-24] Arora y Barak 2009 , pág . 344.

[FOOTNOTERich2008689_(510_in_provided_PDF)-25] Rich 2008 , pág. 689 (510 en el PDF proporcionado).

[FOOTNOTEWatrous20061-26] 1 2 Watrous 2006 , pág. 1.

[FOOTNOTEGoldreich2006255_(2–3_in_provided_pdf)-27] Goldreich 2006 , pág. 255 (2–3 en el pdf proporcionado).

[FOOTNOTEGoldreich2006257_(4_in_provided_pdf)-28] Goldreich 2006 , pág. 257 (4 en el pdf proporcionado).

[FOOTNOTEGoldreich2006266_(11–12_in_provided_pdf)-29] Goldreich 2006 , pág. 266 (11-12 en el pdf proporcionado).

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ a ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]