Clase de complejidad

Conjunto de problemas en la teoría de la complejidad computacional

Una representación de las relaciones entre varias clases de complejidad importantes

En la teoría de la complejidad computacional , una clase de complejidad es un conjunto de problemas computacionales "de complejidad basada en recursos relacionados ". ^[1] Los dos recursos analizados con mayor frecuencia 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 acotado 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 se pueden resolver mediante una máquina de Turing determinista 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 clases de complejidad es un área importante de investigación en la informática teórica. A menudo hay 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 no se conocen; 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 a 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 agrega algún poder computacional a las computadoras y si los problemas que tienen soluciones que se pueden verificar rápidamente para ver si son correctas también se pueden resolver 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 contenidos en ellas con respecto a recursos computacionales particulares como el tiempo o la memoria. Más formalmente, la definición de una clase de complejidad consta de tres cosas: un tipo de problema computacional, un modelo de computación y un recurso computacional acotado. 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 acotados . 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 ser resuelta por un algoritmo . Por ejemplo, "¿es primo el número natural ?" 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 ) está representado por el conjunto de todos los números naturales que son primos: . 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 como sinónimos lenguajes, ya que las cadenas de bits representan lenguajes formales (un concepto tomado de la lingüística ); por ejemplo, decir que el problema está en la clase de complejidad NP es equivalente a decir que el lenguaje está en NP . ${\displaystyle n}$ ${\displaystyle {\texttt {PRIME}}}$ ${\displaystyle {\texttt {PRIME}}=\{n\in \mathbb {N} |n{\text{ is prime}}\}}$ ${\displaystyle {\texttt {PRIME}}}$ ${\displaystyle {\texttt {PRIME}}}$

Problemas de decisión

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

Los problemas que se analizan con más frecuencia en la informática teórica son los problemas de decisión , los tipos 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 que se puede representar con la pregunta de sí o no "¿es primo el número natural ? ". 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, es el conjunto de cadenas que representan números naturales que, cuando se ingresan en una computadora que ejecuta un algoritmo que prueba correctamente la primalidad , el algoritmo responde "sí, este número es primo". Este formato "sí-no" a menudo se enuncia de manera equivalente como "aceptar-rechazar"; es decir, un algoritmo "acepta" una cadena de entrada si la respuesta al problema de decisión es "sí" y "rechaza" si la respuesta es "no". ${\displaystyle n}$ ${\displaystyle {\texttt {PRIME}}}$

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 los que 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 (ver 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 hacen exactas 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 complejidades superfluas del mundo real (como las diferencias en la velocidad del procesador ) que obstruyen la comprensión de los principios fundamentales.

El modelo computacional más comúnmente utilizado es la máquina de Turing . Si bien existen otros modelos y muchas clases de complejidad se definen en función de ellos (ver la sección "Otros modelos de computación"), la máquina de Turing se utiliza para definir las clases de complejidad más básicas. Con la máquina de Turing, en lugar de utilizar unidades estándar de tiempo como el segundo (que hacen imposible separar el tiempo de ejecución de la velocidad del hardware físico) y unidades estándar de memoria 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. Estas se explican con mayor detalle a continuación.

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, en gran parte debido al hecho de que se cree que es 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, entonces 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 cada algoritmo puede representarse como una máquina de Turing.

Mecánicamente, una máquina de Turing (TM) manipula símbolos (generalmente restringidos a los bits 0 y 1 para proporcionar una conexión intuitiva con las computadoras de la vida real) contenidos en una tira de cinta infinitamente larga. La TM puede leer y escribir, uno a la vez, utilizando un cabezal de cinta. El funcionamiento está completamente determinado por un conjunto finito de instrucciones elementales como "en el estado 42, si el símbolo visto es 0, escribe un 1; si el símbolo visto es 1, cambia al estado 17; en el estado 17, si el símbolo visto es 0, escribe un 1 y cambia 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 TM 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 (DTM) es el tipo más básico de máquina de Turing. Utiliza un conjunto fijo de reglas para determinar sus acciones futuras (por eso se la llama " determinista ").

Un problema computacional puede entonces definirse 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 del punto anterior es el conjunto de cadenas (que representan números naturales) que acepta una máquina de Turing que ejecuta un algoritmo que prueba correctamente la primalidad . Se dice que una máquina de Turing reconoce un lenguaje (recordemos que "problema" y "lenguaje" son en gran medida sinónimos en la teoría de la computabilidad y la complejidad) si acepta todas las entradas que están en el lenguaje y se dice que decide un lenguaje si, además, rechaza todas las entradas que no están en el lenguaje (ciertas entradas pueden hacer que una máquina de Turing funcione eternamente, por lo que la decidibilidad impone la restricción adicional sobre la reconocibilidad de que la máquina de Turing debe detenerse en todas las entradas). Una máquina de Turing que "resuelve" un problema generalmente significa que decide el lenguaje. ${\displaystyle {\texttt {PRIME}}}$

Las máquinas de Turing permiten nociones intuitivas de "tiempo" y "espacio". La complejidad temporal de una máquina de Turing en una entrada particular es el número de pasos elementales que la máquina de Turing realiza para alcanzar un estado de aceptación o rechazo. La complejidad espacial es el número de celdas en su cinta que utiliza para alcanzar un estado de aceptación o rechazo.

Máquinas de Turing no deterministas

Comparación entre el cálculo determinista y el no determinista. Si cualquier rama del cálculo no determinista acepta, entonces el NTM acepta.

La máquina de Turing determinista (DTM) es una variante de la máquina de Turing no determinista (NTM). Intuitivamente, una NTM es simplemente una máquina de Turing normal que tiene la capacidad adicional de poder explorar múltiples acciones futuras posibles a partir de un estado dado y "elegir" una rama que acepte (si hay alguna que acepte). Es decir, mientras que una DTM debe seguir solo una rama de cálculo, una NTM puede imaginarse como un árbol de cálculo, que se ramifica en muchas posibles vías de cálculo en cada paso (ver imagen). Si al menos una rama del árbol se detiene con una condición de "aceptación", entonces la NTM acepta la entrada. De esta manera, se puede pensar que una NTM explora simultáneamente todas las posibilidades computacionales en paralelo y selecciona una rama de aceptación. ^[3] Las NTM no están destinadas a ser modelos físicamente realizables, son simplemente máquinas abstractas teóricamente interesantes que dan lugar a una serie de clases de complejidad interesantes (que a menudo tienen definiciones equivalentes físicamente realizables).

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

Los DTM pueden considerarse un caso especial de los NTM que no hacen uso del poder del no determinismo. Por lo tanto, cada cálculo que puede llevarse a cabo con un DTM también puede llevarse a cabo con un NTM equivalente. También es posible simular cualquier NTM utilizando un DTM (el DTM simplemente calculará cada rama computacional posible una por una). Por lo tanto, los dos son equivalentes en términos de computabilidad. Sin embargo, simular un NTM con un DTM a menudo requiere mayor tiempo y/o recursos de memoria; como se verá, cuán significativa es esta desaceleración para ciertas clases de problemas computacionales es una pregunta importante en la teoría de la complejidad computacional.

Límites de recursos

Las clases de complejidad agrupan los problemas computacionales según sus requerimientos de recursos. Para ello, los problemas computacionales se diferencian por 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 entrada. Por ejemplo, la cantidad de tiempo que lleva resolver problemas en la clase de complejidad P crece a una tasa polinómica a medida que aumenta el tamaño de entrada, lo que es comparativamente lento en comparación con los problemas en la clase de complejidad exponencial EXPTIME (o más exactamente, para problemas en EXPTIME que están fuera de P , ya que ). ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {EXPTIME}}}$

Cabe señalar 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 generalmente se preocupan por encontrar la clase de complejidad más pequeña en la que cae un problema y, por lo tanto, se preocupan por identificar en qué clase cae un problema computacional utilizando el algoritmo más eficiente . Puede haber un algoritmo, por ejemplo, que resuelva un problema particular en tiempo exponencial, pero si el algoritmo más eficiente para resolver este problema se ejecuta en tiempo polinómico, entonces la complejidad temporal inherente de ese problema se describe mejor como polinómica.

Límites de tiempo

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

En la teoría de la complejidad computacional, los científicos informáticos teóricos se preocupan menos de los valores de tiempo de ejecución particulares y más de la clase general de funciones a las que pertenece la función de complejidad temporal. Por ejemplo, ¿la función de complejidad temporal es 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 la máquina de Turing es la cantidad de celdas en la cinta de la máquina de Turing que se requieren para ejecutar un algoritmo en un tamaño de entrada determinado. Formalmente, la complejidad espacial de un algoritmo implementado con una máquina de Turing se define como la función , donde es la cantidad máxima de celdas que utiliza en cualquier entrada de longitud . ${\displaystyle M}$ ${\displaystyle s_{M}:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle s_{M}(n)}$ ${\displaystyle M}$ ${\displaystyle n}$

Clases de complejidad básica

Definiciones básicas

Las clases de complejidad suelen definirse utilizando conjuntos granulares de clases de complejidad denominados DTIME y NTIME (para la complejidad temporal) y DSPACE y NSPACE (para la complejidad espacial). Utilizando la notación O mayúscula , se definen de la siguiente manera:

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

Clases de complejidad temporal

P y NP

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

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

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

A menudo se dice que P es la clase de problemas que se pueden resolver "rápidamente" o "eficientemente" mediante una computadora determinista, ya que la complejidad temporal de resolver un problema en P aumenta relativamente lentamente con el tamaño de entrada.

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

NP es la clase de lenguajes para los que existe una máquina de Turing determinista en tiempo polinomial y un polinomio tal que para todo , es en si y sólo si existe alguno que acepte. ${\displaystyle L}$ ${\displaystyle M}$ ${\displaystyle p}$ ${\displaystyle w\in \{0,1\}^{*}}$ ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle c\in \{0,1\}^{p(|w|)}}$ ${\displaystyle M(w,c)}$

Esta equivalencia entre la definición no determinista y la definición de verificador resalta una conexión fundamental entre el no determinismo y la verificabilidad de la solución. Además, también proporciona un método útil para demostrar que un idioma está en NP : basta con identificar un certificado adecuado y demostrar que se puede verificar en tiempo polinómico.

El problema de P versus NP

Aunque puede parecer que hay una diferencia obvia entre la clase de problemas que se pueden resolver de manera eficiente y la clase de problemas cuyas soluciones son simplemente comprobables de manera eficiente, P y NP están en realidad en el centro de uno de los problemas sin resolver más famosos en la ciencia de la computación: el problema P versus NP . Si bien se sabe que (intuitivamente, las máquinas de Turing deterministas son solo una subclase de las máquinas de Turing no deterministas que no hacen uso de 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 posibles ramas de la computación proporciona como máximo una aceleración polinomial sobre poder explorar solo una sola rama. Además, se seguiría que si existe una prueba para una instancia de problema y esa prueba puede verificarse rápidamente para ver si es correcta (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 abrumadora mayoría de los científicos informáticos creen que , ^[7] y la mayoría de los esquemas criptográficos empleados hoy en día se basan en el supuesto de que . ^[8] ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {NP}}}$ ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$

EXPTIME y NEXPTIME

EXPTIME (a veces abreviado como EXP ) es la clase de problemas de decisión que se pueden resolver con 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 se pueden resolver con una máquina de Turing no determinista en tiempo exponencial. O más formalmente,

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

${\displaystyle {\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 da el caso de que EXPTIME es NEXPTIME . No se sabe si esto es correcto, pero si P = NP , EXPTIME debe ser igual a NEXPTIME . ${\displaystyle \subseteq }$

Clases de complejidad espacial

L y NL

Si bien 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 la entrada completa (porque ). ^{[a] [9]} Sin embargo, hay una cantidad significativa de problemas que se pueden resolver en el espacio logarítmico. Las definiciones de estas clases requieren una máquina de Turing de dos cintas para que sea posible que la máquina almacene la entrada completa (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 la cantidad de celdas que se utilizan en la cinta de trabajo. ${\displaystyle \log n<n}$

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

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

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

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

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 que se pueden resolver en el espacio polinomial mediante una máquina de Turing determinista y NPSPACE es la clase de problemas que se pueden resolver en el espacio polinomial mediante una máquina de Turing no determinista. Más formalmente,

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

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

Si bien no se sabe si P = NP , el teorema de Savitch demostró que PSPACE = NPSPACE . También se sabe que , lo que 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 una unidad de tiempo, una máquina de Turing que funciona en tiempo polinomial solo puede escribir en una cantidad polinomial de celdas. Se sospecha que P es estrictamente menor que PSPACE , pero esto no se ha demostrado. ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {PSPACE}}}$

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 que se pueden resolver en el espacio exponencial mediante una máquina de Turing determinista y NEXPSPACE es la clase de problemas que se pueden resolver en el espacio exponencial mediante una máquina de Turing no determinista. O más formalmente,

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

${\displaystyle {\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 tienen una variedad de propiedades de cierre . Por ejemplo, las clases de decisión pueden estar cerradas bajo negación , disyunción , conjunción o incluso bajo todas las operaciones booleanas . Además, también pueden estar cerradas bajo una variedad de esquemas de cuantificación. P , por ejemplo, está cerrada bajo todas las operaciones booleanas y bajo la cuantificación sobre dominios de tamaño polinomial. Las propiedades de cierre pueden ser útiles para separar clases: una ruta posible 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 está cerrada bajo la negación tiene una clase complementaria co-X , que consiste en los complementos de los lenguajes contenidos en X (es decir, co -NP ). co-NP , por ejemplo, es una clase de complejidad complementaria importante y se encuentra en el centro del problema sin resolver sobre si co-NP = NP . ${\displaystyle {\textsf {co-X}}=\{L|{\overline {L}}\in {\mathsf {X}}\}}$

Las propiedades de cierre son una de las razones clave por las que muchas clases de complejidad se definen de la forma en que lo están. ^[11] Tomemos, por ejemplo, un problema que se puede resolver en el tiempo (es decir, en tiempo lineal) y uno que se puede resolver, en el mejor de los casos, en tiempo. Ambos problemas están en P , pero el tiempo de ejecución del segundo crece considerablemente más rápido que el tiempo de ejecución del primero a medida que aumenta el tamaño de entrada. Uno podría preguntarse si sería mejor definir la clase de problemas "eficientemente solucionables" utilizando algún límite polinómico más pequeño, como , 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 está cerrada bajo la adición, la multiplicación y la composición (por ejemplo, , que es un polinomio pero ). ^[11] Dado que nos gustaría que componer un algoritmo eficiente con otro algoritmo eficiente todavía se considere 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 orden bajo, y casi todos los problemas fuera de P que son prácticamente útiles no tienen algoritmos conocidos con tiempos de ejecución exponenciales pequeños, es decir, con tiempos de ejecución donde c está cerca de 1. ^[13] ) ${\displaystyle O(n)}$ ${\displaystyle O(n^{1000})}$ ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{3})\circ O(n^{2})=O(n^{6})}$ ${\displaystyle O(n^{6})>O(n^{3})}$ ${\displaystyle O(c^{n})}$

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 problema, es decir, una reducción toma entradas de un problema y las transforma en entradas de otro problema. Por ejemplo, puede reducir la suma ordinaria en base 10 a la suma en base 2 transformando y a su notación en base 2 (por ejemplo, 5+7 se convierte en 101+111). Formalmente, un problema se reduce a un problema si existe una función tal que para cada , si y solo si . ${\displaystyle x+y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle f}$ ${\displaystyle x\in \Sigma ^{*}}$ ${\displaystyle x\in X}$ ${\displaystyle f(x)\in Y}$

En general, 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 nos interesa utilizar una reducción en tiempo polinómico, ya que cualquier problema que se pueda reducir de manera eficiente a otro problema no es más difícil que . Formalmente, un problema es reducible en tiempo polinómico a un problema si existe una función computable en tiempo polinómico tal que para todo , si y solo si . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle p}$ ${\displaystyle x\in \Sigma ^{*}}$ ${\displaystyle x\in X}$ ${\displaystyle p(x)\in Y}$

Tenga en cuenta que las reducciones se pueden definir de muchas maneras diferentes. Las reducciones más 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 es difícil para una clase de problemas C si cada problema en C puede reducirse en tiempo polinómico a . Por lo tanto, ningún problema en C es más difícil que , ya que un algoritmo para nos permite resolver cualquier problema en C con una desaceleración polinómica como máximo. De particular importancia, el conjunto de problemas que son difíciles para NP se llama el conjunto de problemas NP-difíciles . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

Lo completo

Si un problema es difícil para C y también lo es en C , entonces se dice que es completo para C. Esto significa que es el problema más difícil en C (ya que podría haber muchos problemas que sean igualmente difíciles, más precisamente es tan difícil como los problemas más difíciles en C ). ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

De particular importancia es la clase de problemas NP -completos , los problemas más difíciles en NP . Debido a que todos los problemas en NP pueden ser reducidos en tiempo polinómico a problemas NP -completos, encontrar un problema NP -completo que pueda ser resuelto en tiempo polinómico 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 el espacio, entonces una máquina de Turing determinista puede resolver el mismo problema en el espacio, es decir, en el cuadrado del espacio. Formalmente, el teorema de Savitch establece que para cualquier , ^[14] ${\displaystyle f(n)}$ ${\displaystyle f(n)^{2}}$ ${\displaystyle f(n)>n}$

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

Corolarios importantes del teorema de Savitch son que PSPACE = NPSPACE (ya que el cuadrado de un polinomio sigue siendo un polinomio) y EXPSPACE = NEXPSPACE (ya que el cuadrado de un exponencial sigue siendo un exponencial).

Estas relaciones dan respuesta a preguntas fundamentales sobre el poder del no determinismo en comparación con el determinismo. En concreto, el teorema de Savitch muestra que cualquier problema que una máquina de Turing no determinista pueda resolver en el espacio polinómico, una máquina de Turing determinista también puede resolverlo en el espacio polinómico. De forma similar, 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 espacio exponencial.

Teoremas de jerarquía

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

El teorema de la jerarquía temporal establece que

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

El teorema de jerarquía espacial establece que

${\displaystyle {\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 forman 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.
• Se definen varias clases 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 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 de forma probabilística 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 está destinada a aceptar pueden en algunas ocasiones ser rechazadas y las cadenas que la máquina de Turing está destinada a rechazar pueden en algunas ocasiones ser aceptadas. Como resultado, las clases de complejidad basadas en la máquina de Turing probabilística se definen en gran parte en torno a la cantidad de error que se permite. Formalmente, se definen utilizando una probabilidad de error . Se dice que una máquina de Turing probabilística reconoce un lenguaje con probabilidad de error si: ${\displaystyle \epsilon }$ ${\displaystyle M}$ ${\displaystyle L}$ ${\displaystyle \epsilon }$

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

Clases de complejidad importantes

Relaciones entre las clases de complejidad probabilística fundamental. BQP es una clase de complejidad cuántica probabilística y se describe en la sección de computación cuántica.

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

La clase más estricta es ZPP (tiempo polinomial probabilístico de error cero), la clase de problemas resolubles en tiempo polinomial por 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 tipo de error .

Una clase ligeramente más flexible es RP (tiempo polinomial aleatorio), que no mantiene ningún error para cadenas que no están en el lenguaje, pero permite un error acotado para cadenas en el lenguaje. Más formalmente, un lenguaje está en RP si hay una máquina de Turing de tiempo polinomial probabilística tal que si una cadena no está en el lenguaje, entonces siempre rechaza y si una cadena está en el lenguaje, entonces acepta con una probabilidad de al menos 1/2. La clase co-RP se define de manera similar, excepto que los roles están invertidos: no se permite el error para cadenas en el lenguaje, pero sí para cadenas que no están en el lenguaje. Tomadas en conjunto, las clases RP y co-RP abarcan todos los problemas que pueden resolverse mediante máquinas de Turing probabilísticas con error unilateral . ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

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

La clase más amplia de problemas probabilísticos solucionables de manera eficiente es PP (tiempo polinomial probabilístico), el conjunto de lenguajes que se pueden resolver mediante una máquina de Turing probabilística en tiempo polinomial con una probabilidad de error de menos de 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: . Es decir, ZPP consiste exactamente 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 error unilateral: co-RP no permite error para cadenas en el lenguaje y RP no permite error 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 error para cadenas tanto en el lenguaje como fuera de él (es decir, ningún error en absoluto), que es exactamente la definición de ZPP . ${\displaystyle {\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}}$

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

Sistemas de prueba interactivos

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

Representación general de un protocolo de prueba interactivo

Los sistemas de prueba interactivos son máquinas abstractas que modelan la computación como el intercambio de mensajes entre dos partes: un probador y un verificador . Las partes interactúan intercambiando mensajes, y una cadena de entrada es aceptada por el sistema si el verificador decide aceptar la entrada sobre la base de los mensajes que ha recibido del probador. El probador tiene un poder computacional ilimitado mientras que el verificador tiene un poder computacional limitado (la definición estándar de los sistemas de prueba interactivos define al verificador como limitado en el tiempo polinomial). El probador, sin embargo, no es confiable (esto evita que todos los idiomas sean reconocidos trivialmente por el sistema de prueba al hacer que el probador computacionalmente ilimitado resuelva si una cadena está en un idioma y luego envíe un "SÍ" o "NO" confiable al verificador), por lo que el verificador debe realizar un "interrogatorio" del probador "preguntándole" rondas sucesivas de preguntas, aceptando solo si desarrolla un alto grado de confianza en que la cadena está en el idioma. ^[15] ${\displaystyle P}$ ${\displaystyle V}$ ${\displaystyle P}$

Clases de complejidad importantes

La clase NP es un sistema de prueba simple en el que el verificador está restringido a ser una máquina de Turing determinista en tiempo polinomial y el procedimiento está restringido a una ronda (es decir, el probador envía solo una prueba completa, generalmente denominada certificado , al verificador). Dicho de otra manera, 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) es 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 llamarse dIP (prueba interactiva determinista), aunque rara vez se hace referencia a ella como tal.

Resulta que NP captura todo el poder 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 necesitar más de una sola ronda de mensajes entre el probador y el verificador. Los sistemas de prueba interactivos que proporcionan un mayor poder computacional sobre las clases de complejidad estándar requieren 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 el cálculo aleatorio , los algoritmos probabilísticos introducen error 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 . ${\displaystyle \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 que se pueden resolver mediante un sistema de prueba interactivo , donde es un tiempo polinomial probabilístico y el sistema de prueba satisface dos propiedades: para un lenguaje ${\displaystyle (P,V)}$ ${\displaystyle V}$ ${\displaystyle L\in {\mathsf {IP}}}$

1. ( Completitud ) una cadena implica ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle \Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\geq {\tfrac {2}{3}}}$
2. (Solidez) una cadena no implica ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle \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 resolverse mediante un sistema de prueba interactivo en tiempo polinomial también puede resolverse mediante una máquina de Turing determinista con recursos espaciales polinomiales, y viceversa.

Una modificación del protocolo para IP produce otra clase de complejidad importante: AM (protocolo Arthur-Merlin). En la definición de los 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 estas monedas. Por esta razón, las monedas se denominan monedas aleatorias privadas . El sistema de prueba interactivo se puede restringir 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 acepta o rechaza aplicando una función de tiempo polinomial determinista al mensaje del probador. AM se puede generalizar 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 el caso que para todo , AM [ k ]= AM [2]. También es el caso que . ${\displaystyle k\geq 2}$ ${\displaystyle {\mathsf {AM}}[k]\subseteq {\mathsf {IP}}[k]}$

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

Circuitos booleanos

Ejemplo de circuito booleano que calcula la función booleana , con entradas de ejemplo , , y . Los nodos son puertas AND , los nodos son puertas OR y los nodos son puertas NOT . ${\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})}$ ${\displaystyle x_{1}=0}$ ${\displaystyle x_{2}=1}$ ${\displaystyle x_{3}=0}$ ${\displaystyle \wedge }$ ${\displaystyle \vee }$ ${\displaystyle \neg }$

Un modelo alternativo de computación a la máquina de Turing es el circuito booleano , un modelo simplificado de los circuitos digitales que se utilizan en las computadoras modernas . Este modelo no solo proporciona una conexión intuitiva entre la computación en teoría y la computación en 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 algoritmos diferentes).

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

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

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 (la cantidad de vértices del circuito). La complejidad de tamaño de una familia de circuitos es la función , donde es el tamaño del circuito de . Las clases de funciones conocidas se derivan naturalmente de esto; por ejemplo, una familia de circuitos de tamaño polinomial es aquella en la que la función es un polinomio . ${\displaystyle (C_{0},C_{1},C_{2},...)}$ ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle f(n)}$ ${\displaystyle C_{n}}$ ${\displaystyle f}$

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 hay una conexión natural entre la complejidad del circuito y la complejidad temporal. Intuitivamente, un lenguaje con una complejidad temporal pequeña (es decir, requiere relativamente pocas operaciones secuenciales en una máquina de Turing), también tiene una complejidad de circuito pequeña (es decir, requiere relativamente pocas operaciones booleanas). Formalmente, se puede demostrar que si un lenguaje está en , donde es una función , entonces tiene una complejidad de circuito . ^[16] Se sigue directamente de este hecho que . En otras palabras, cualquier problema que pueda resolverse en tiempo polinomial por una máquina de Turing determinista también puede resolverse por una familia de circuitos de tamaño polinomial. Se da además el caso de que la inclusión sea adecuada, es decir (por ejemplo, hay algunos problemas indecidibles que están en P/poly ). ${\displaystyle {\mathsf {DTIME}}(t(n))}$ ${\displaystyle t}$ ${\displaystyle t:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle O(t^{2}(n))}$ ${\displaystyle {\mathsf {\color {Blue}P}}\subset {\textsf {P/poly}}}$ ${\displaystyle {\textsf {P}}\subsetneq {\textsf {P/poly}}}$

P/poly tiene varias 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 . ^[17] P/poly también es útil para investigar propiedades de la jerarquía polinómica . Por ejemplo, si NP ⊆ P/poly , entonces PH colapsa a . 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 de manera equivalente como la clase de lenguajes reconocidos por una máquina de Turing de tiempo polinómico con una función de asesoramiento acotada por polinomios . ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ ${\displaystyle \Sigma _{2}^{\mathsf {P}}}$

Dos subclases de P/poly que tienen propiedades interesantes por derecho propio son NC y AC . Estas clases se definen no solo en términos de su tamaño de circuito sino también en términos de su profundidad . La profundidad de un circuito es la longitud de la ruta dirigida más larga desde un nodo de entrada hasta el nodo de salida. La clase NC es el conjunto de lenguajes que pueden ser resueltos por familias de circuitos que están restringidas no solo a tener tamaño polinomial sino también a tener profundidad polilogarítmica. La clase AC se define de manera similar a NC , sin embargo, se permite que las puertas tengan un abanico de entrada ilimitado (es decir, las puertas AND y OR se pueden aplicar a más de dos bits). NC es una clase notable porque puede definirse de manera equivalente como la clase de lenguajes que tienen algoritmos paralelos eficientes .

Computación cuántica

Las clases BQP y QMA , que son de importancia clave en la ciencia de la información cuántica , se definen utilizando máquinas de Turing cuánticas .

Otros tipos de problemas

Si bien la mayoría de las clases de complejidad estudiadas por los científicos informáticos son conjuntos de problemas de decisión , también hay varias 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 . Estos se explican con mayor detalle a continuación.

Problemas de conteo

Un problema de conteo no sólo pregunta si existe una solución (como en un problema de decisión ), sino que pregunta cuántas soluciones existen. ^[18] Por ejemplo, el problema de decisión pregunta si un gráfico particular tiene un ciclo simple (la respuesta es un simple sí/no); el problema de conteo correspondiente (pronunciado "ciclo agudo") pregunta cuántos ciclos simples tiene. ^[19] La salida de un problema de conteo es, por 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] ${\displaystyle {\texttt {CYCLE}}}$ ${\displaystyle G}$ ${\displaystyle \#{\texttt {CYCLE}}}$ ${\displaystyle G}$

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 tal que para cada entrada , es el número de soluciones. Por ejemplo, en el problema, la entrada es un gráfico (un gráfico representado como una cadena de bits ) y es el número de ciclos simples en . ${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$ ${\displaystyle w\in \{0,1\}^{*}}$ ${\displaystyle f(w)}$ ${\displaystyle \#{\texttt {CYCLE}}}$ ${\displaystyle G\in \{0,1\}^{*}}$ ${\displaystyle f(G)}$ ${\displaystyle G}$

Los problemas de conteo surgen en varios campos, incluida 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 aguda") es una clase importante de problemas de conteo que pueden 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 cómputo de una máquina de Turing no determinista . #P se define formalmente de la siguiente manera:

#P es el conjunto de todas las funciones tales que existe una máquina de Turing no determinista en tiempo polinomial tal que para todo , es igual al número de ramas de aceptación en el árbol de cálculo de en . ^[22] ${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$ ${\displaystyle M}$ ${\displaystyle w\in \{0,1\}^{*}}$ ${\displaystyle f(w)}$ ${\displaystyle M}$ ${\displaystyle w}$

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 ), así también #P puede definirse de manera equivalente en términos de un verificador. Recordemos que un problema de decisión es NP si existe un certificado verificable en tiempo polinomial para una instancia de problema dada; es decir, NP pregunta si existe una prueba de membresía (un certificado) para la entrada cuya corrección pueda verificarse en tiempo polinomial. La clase #P pregunta cuántos certificados de este tipo existen. ^[22] En este contexto, #P se define de la siguiente manera:

#P es el conjunto de funciones tales que existe un polinomio y una máquina de Turing de tiempo polinomial (el verificador), tales que para cada , . ^[23] En otras palabras, es igual al tamaño del conjunto que contiene todos los certificados de tamaño polinomial para . ${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$ ${\displaystyle p:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle V}$ ${\displaystyle w\in \{0,1\}^{*}}$ ${\displaystyle f(w)={\Big |}{\big \{}c\in \{0,1\}^{p(|w|)}:V(w,c)=1{\big \}}{\Big |}}$ ${\displaystyle f(w)}$ ${\displaystyle w}$

Problemas de función

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

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

Un algoritmo resuelve si para cada entrada tal que existe un satisfactorio , el algoritmo produce uno de esos . Esta es otra forma de decir que es una función y el algoritmo resuelve para todos los . ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (x,y)\in R}$ ${\displaystyle y}$ ${\displaystyle f}$ ${\displaystyle f(x)}$ ${\displaystyle 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 función que pueden ser resueltos por una máquina de Turing determinista en tiempo polinomial . ^[23] FP puede ser considerado como el problema de función equivalente de P . Es importante destacar que FP proporciona cierta información tanto para problemas de conteo como para P versus NP . Si #P = FP , entonces las funciones que determinan la cantidad de certificados para problemas en NP son eficientemente resolubles. Y dado que calcular la cantidad de certificados es al menos tan difícil como determinar si existe un certificado, debe seguir 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 promesa

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

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

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

La entrada a un algoritmo para un problema de promesa es, por tanto , , que se denomina promesa . Se dice que las cadenas en satisfacen la promesa . ^[25] Por definición, y deben ser disjuntos, es decir, . ${\displaystyle M}$ ${\displaystyle (\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})}$ ${\displaystyle \Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}}$ ${\displaystyle \Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}}$ ${\displaystyle \Pi _{\text{ACCEPT}}}$ ${\displaystyle \Pi _{\text{REJECT}}}$ ${\displaystyle \Pi _{\text{ACCEPT}}\cap \Pi _{\text{REJECT}}=\emptyset }$

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

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

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, se puede definir 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 está en P si existe un algoritmo de tiempo polinomial tal que: ${\displaystyle (\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})}$ ${\displaystyle M}$

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

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

La formulación de 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 la formulación de problemas de promesa ha sido útil para los científicos informáticos. Los problemas de promesa, por ejemplo, han desempeñado un papel clave 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 los 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 descomposición en decidibles e indecidibles pertenece más al estudio de la teoría de la computabilidad , pero es útil para poner las clases de complejidad en perspectiva.

Véase también

• Lista de clases de complejidad

Notas

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

Referencias

1. Johnson (1990).
2. Arora y Barak 2009, pág. 28.
3. Sipser 2006, pág. 48, 150.
4. Sipser 2006, pág. 255.
5. Aaronson 2017, pág. 12.
6. Aaronson 2017, pág. 3.
7. Gasarch 2019.
8. Aaronson 2017, pág. 4.
9. Sipser 2006, pág. 320.
10. Sipser 2006, pág. 321.
11. Aaronson 2017, pág. 7.
12. Aaronson 2017, pág. 5.
13. Aaronson 2017, pág. 6.
14. Lee 2014.
15. Arora y Barak 2009, pág. 144.
16. Sipser 2006, pág. 355.
17. Arora y Barak 2009, pág. 286.
18. Fortnow 1997.
19. Arora 2003.
20. Arora y Barak 2009, pág. 342.
21. Arora y Barak 2009, pág. 341–342.
22. 2006.
23. Arora y Barak 2009, pag. 344.
24. Rich 2008, pág. 689 (510 en el PDF proporcionado).
25. Watrous 2006, pág. 1.
26. Goldreich 2006, pag. 255 (2–3 en el pdf proporcionado).
27. Goldreich 2006, pag. 257 (4 en el pdf proporcionado).
28. Goldreich 2006, pag. 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 de Ciencias Weizmann. Archivado desde el original el 17 de junio de 2020.
• Arora, Sanjeev ; Barak, Boaz (2009). Computational Complexity: A Modern Approach . Cambridge University Press. Borrador. Archivado desde el 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 desde el original el 21 de mayo de 2022.
• Barak, Boaz (primavera de 2006). "Complejidad del conteo" (PDF) . Ciencias de la Computación 522: Computacional Complejidad . Universidad de Princeton . Archivado desde el 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. págs. 81–106. ISBN. 9780387949734Archivado desde el 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). "Problemas de promesas: una encuesta" (PDF) . En Goldreich, Oded; Rosenberg, Arnold L.; Selman, Alen L. (eds.). Ciencias de la computación teóricas. Apuntes de clase en ciencias de la computación, vol. 3895 (PDF) . Apuntes de clase en ciencias de la computación. Vol. 3895. Springer. págs. 254–290. doi :10.1007/11685654_12. ISBN. 978-3-540-32881-0. Archivado (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.
• Lee, James R. (22 de mayo de 2014). "Lecture 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 . Consultado el 5 de octubre de 2022 .
• Rich, Elaine (2008). Autómatas, computabilidad y complejidad: teoría y aplicaciones (PDF) . Prentice Hall . ISBN 978-0132288064. Archivado (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-3. Archivado 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.

Lectura adicional

• El zoológico de la complejidad Archivado el 27 de agosto de 2019 en Wayback Machine : Una lista enorme de clases de complejidad, una referencia para expertos.
• Neil Immerman . "Teoría de la complejidad computacional". Archivado desde el original el 16 de abril de 2016.Incluye un diagrama que muestra la jerarquía de las clases de complejidad y cómo encajan entre sí.
• Michael Garey y David S. Johnson : Computers and Intractability: A Guide to the Theory of NP-Completeness. Nueva York: WH Freeman & Co., 1979. La referencia estándar sobre problemas NP-completos: una categoría importante de problemas cuyas soluciones parecen requerir un tiempo imprácticamente largo para su cálculo.