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 relacionada con los recursos . Los dos recursos más comúnmente analizados 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 cálculo 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 puede resolver una máquina de Turing determinista en tiempo polinomial . Sin embargo, hay muchas clases de complejidad definidas en términos de otros tipos de problemas (por ejemplo, problemas de conteo y problemas de función) y el uso de otros modelos de computación (por ejemplo , máquinas probabilísticas de Turing , 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 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: NL P NP PSPACE EXPTIME EXPSPACE (donde denota la relación de subconjunto ). Sin embargo, aún no se conocen muchas relaciones; por ejemplo, uno de los problemas abiertos más famosos de la informática se refiere a si P es igual o no a NP . Las relaciones entre clases a menudo responden preguntas sobre la naturaleza fundamental de la computación. El${\displaystyle \subseteq }$${\displaystyle \subseteq }$${\displaystyle \subseteq }$${\displaystyle \subseteq }$${\displaystyle \subseteq }$${\displaystyle \subseteq }$El problema P versus NP , por ejemplo, está directamente relacionado con preguntas de si el no determinismo agrega poder computacional a las computadoras y si los problemas que tienen una solución que se puede verificar rápidamente para verificar su corrección también se pueden resolver rápidamente.

Antecedentes

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 ellos 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 limitados . Por ejemplo, la clase de complejidad P se define como el conjunto de problemas de decisiónque puede resolverse mediante una máquina de Turing determinista en tiempo polinomial .

Problemas computacionales

Intuitivamente, un problema computacional es solo una pregunta que una computadora puede responder. Por ejemplo, "¿el número natural es primo ?" es un problema que una computadora podría resolver. Un problema de cálculo se representa matemáticamente como el conjunto de respuestas al problema. En el ejemplo de primalidad, el problema (lo llaman ) está representado por el conjunto de 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${\displaystyle n}$ ${\displaystyle PRIME}$${\displaystyle PRIME=\{n\in \mathbb {N} |n{\text{ is prime}}\}}$. Por esta razón, los problemas computacionales se denominan a menudo como sinónimo de lenguajes ; por ejemplo, decir que el problema está en la clase de complejidad NP equivale a decir que el idioma está en NP .${\displaystyle PRIME}$${\displaystyle PRIME}$

Problemas de decisión

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

Los problemas que se analizan con mayor frecuencia en la informática teórica son los problemas de decisión , los tipos de problemas que pueden plantearse como preguntas de sí o no . El ejemplo de primalidad anterior, por ejemplo, es un ejemplo de un problema de decisión, ya que puede ser representado por la pregunta sí-no "es el número natural 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 al 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${\displaystyle n}$ ${\displaystyle PRIME}$, el algoritmo responde "sí, este número es primo". Este formato "sí-no" a menudo se expresa 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".

Si bien algunos problemas no pueden expresarse fácilmente como problemas de decisión, no obstante abarcan una amplia gama de problemas computacionales. ^[1] 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 y problemas de promesa (consulte la sección "Otros tipos de problemas").

Modelos computacionales

Para concretar la noción de "computadora", en la informática teórica se analizan problemas en el contexto de un modelo computacional . Esto también es directamente relevante para hacer nociones exactas de recursos computacionales como "tiempo" y "memoria". En la teoría de la complejidad computacional , las clases de complejidad se ocupan de lo inherenterequisitos de recursos de los problemas y no 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 obstruyen 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 términos de ellos (consulte la sección "Otros modelos de cálculo" ), 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 estándar de tiempo como la segunda (que hacen imposible separar el tiempo de ejecución de la velocidad del hardware físico) y unidades estándar de memoria como bytes , la noción de tiempo se abstrae como el número de elementos elementales. pasos que toma una máquina de Turing 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. Estos se explican con mayor detalle a continuación.

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

Máquinas deterministas de Turing

Artículo principal: máquina de Turing

Una 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 informática general. Es el modelo más utilizado en la teoría de la complejidad, debido en gran parte al hecho de que se cree que es tan poderoso como cualquier otro modelo de cálculo y es fácil de analizar matemáticamente. Es importante destacar que se cree que si existe un algoritmo que resuelve un problema en 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 a computadoras de la vida real) contenidos en una tira de cinta infinitamente larga. El TM puede leer y escribir, uno a la vez, usando un cabezal de cinta. La operación está totalmente determinada por un conjunto finito de instrucciones elementales como "en el estado 42, si el símbolo visto es 0, escriba un 1; si el símbolo visto es 1, cambie al estado 17; en el estado 17, si el símbolo visto es 0, escriba un 1 y cambie al estado 6 ". La máquina de Turing comienza con solo la cadena de entrada en su cinta y deja en blanco en todas partes. El TM acepta la entrada si entra en un estado de aceptación designado y rechaza la entrada 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 llama "determinista ").

Entonces, un problema computacional puede 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 de arriba 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 (recuerde que "problema" y "lenguaje" son en gran parte 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 entradas que no están en el idioma (ciertas entradas pueden hacer que una máquina de Turing funcione para siempre, por lo que la decisión${\displaystyle PRIME}$coloca la restricción adicional sobre el reconocimiento de que la máquina de Turing debe detenerse en todas las entradas). Una máquina de Turing que "resuelve" un problema generalmente significa una que decide el idioma.

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

Máquinas de Turing no deterministas

Artículo principal: máquina de Turing no determinista

Una comparación de cálculo determinista y no determinista. Si acepta alguna rama del cálculo no determinista, entonces la NTM acepta.

Una variante de la máquina de Turing determinista (DTM) es 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 desde un estado dado y "elegir" una rama que acepta (si alguna acepta). Es decir, mientras que un DTM debe seguir solo una rama de cálculo, un NTM se puede imaginar como un árbol de cálculo, ramificándose en muchas vías computacionales posibles en cada paso (ver imagen). Si al menos una rama del árbol se detiene con una condición de "aceptar", 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. ^[2] Las MNA 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).

Las DTM pueden verse como un caso especial de MNA que no hacen uso del poder del no determinismo. Por lo tanto, todos los cálculos que puede realizar un DTM también pueden ser realizados por un NTM equivalente. También es posible simular cualquier NTM utilizando un DTM. Por tanto, los dos son equivalentes en términos de computabilidad. Sin embargo, la simulación de un NTM con un DTM a menudo requiere más tiempo y / o recursos de memoria; Como se verá, la importancia de esta desaceleración para ciertas clases de problemas computacionales es una cuestión importante en la teoría de la complejidad computacional.

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

Límites de recursos

Las clases de complejidad agrupan los problemas computacionales según sus necesidades de recursos. Para hacer esto, los problemas computacionales se diferencian por límites superiores en la cantidad máxima de recursos que toma el algoritmo más eficiente para resolverlos. Más particularmente, las clases de complejidad están relacionadas con la tasa de crecimiento de los requisitos de recursos para resolver un problema computacional a medida que aumenta el tamaño de la entrada. Por ejemplo, la cantidad de tiempo que se tarda en resolver problemas en la clase de complejidad P crece relativamente lentamente a medida que aumenta el tamaño de entrada, mientras que crece comparativamente rápido para problemas en la clase de complejidad EXPTIME (o más exactamente, para problemas en EXPTIME que están fuera de de P, desde P EXPTIME ). Este proceso se formaliza mediante la notación O grande .${\displaystyle \subseteq }$

Tenga en cuenta que el estudio de las clases de complejidad está destinado principalmente a comprender la complejidad inherente requerida 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, están interesados ​​en 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 polinomial, entonces la complejidad de tiempo inherente de ese problema se describe mejor como polinomio.

Límites de tiempo

Artículo principal: complejidad del 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 en un tamaño de entrada dado. Formalmente, la complejidad de tiempo para 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 toma cualquier entrada de longitud . Por ejemplo, digamos que las entradas a son números binarios. Luego hay, por ejemplo, cuatro entradas de tamaño dos: 00, 01, 10 y 11. Digamos que correr en 00 requiere diez pasos, en 01 toma doce pasos, en 10 toma ocho pasos y en 11 toma quince pasos. El tiempo de ejecución es el máximo de estas cuatro tiempos de funcionamiento: .${\displaystyle M}$${\displaystyle t_{M}:\mathbb {N} \to \mathbb {N} }$${\displaystyle t_{M}(n)}$${\displaystyle M}$${\displaystyle n}$${\displaystyle M}$${\displaystyle M}$${\displaystyle t_{M}(2)}$${\displaystyle t_{M}(2)=15}$

Sin embargo, las clases de complejidad se preocupan menos por valores de tiempo de ejecución particulares y más por la clase general de funciones en las que cae la función de complejidad de tiempo. Por ejemplo, ¿es la complejidad del tiempo un polinomio ? ¿Una función logarítmica ? ¿Una función exponencial ? ¿O otro tipo de función? Dado que las funciones de complejidad de tiempo exacto a menudo son expresiones complicadas, se simplifican mediante la notación O grande . Esto conduce a los conjuntos más básicos de clases de complejidad temporal: DTIME y NTIME . Se definen de la siguiente manera:

• La clase de complejidad del tiempo es la colección de todos los problemas que son decidibles por una máquina de Turing determinista del tiempo.${\displaystyle {\mathsf {DTIME}}(t(n))}$${\displaystyle O(t(n))}$
• La clase de complejidad del tiempo es la colección de todos los problemas que son decidibles por una máquina de Turing no determinista en el tiempo.${\displaystyle {\mathsf {NTIME}}(t(n))}$${\displaystyle O(t(n))}$

Por ejemplo, si un problema puede resolverse mediante un algoritmo que se ejecuta en el tiempo, entonces está en DTIME desde . Tenga en cuenta que en virtud de la notación O grande es también el caso de que , y así sucesivamente. Esto significa que las clases DTIME generalmente no son mutuamente excluyentes sino que forman una jerarquía: DTIME DTIME DTIME . Esta naturaleza jerárquica aparece con frecuencia entre las clases de complejidad.${\displaystyle X}$${\displaystyle t(n)=8n^{3}+2n+4}$${\displaystyle (n^{3})}$${\displaystyle t(n)=8n^{3}+2n+4=O(n^{3})}$${\displaystyle 8n^{3}+2n+4=O(n^{4})}$${\displaystyle 8n^{3}+2n+4=O(n^{5})}$${\displaystyle (n^{3})\subseteq }$${\displaystyle (n^{4})\subseteq }$${\displaystyle (n^{5})\subseteq \cdots }$

Límites de espacio

Artículo principal: Complejidad espacial

La complejidad espacial de un algoritmo con respecto al modelo de la 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 en un tamaño de entrada dado. Formalmente, la complejidad espacial de un algoritmo implementado con una máquina de Turing se define como la función , donde es el número máximo de celdas que se utiliza en cualquier entrada de longitud .${\displaystyle M}$${\displaystyle s_{M}:\mathbb {N} \to \mathbb {N} }$${\displaystyle s_{M}(n)}$${\displaystyle M}$${\displaystyle n}$

Las clases de complejidad espacial más básicas se definen de la siguiente manera:

• La clase de complejidad espacial es la colección de todos los problemas que son decidibles por una máquina de Turing determinista del espacio.${\displaystyle {\mathsf {DSPACE}}(s(n))}$${\displaystyle O(s(n))}$
• La clase de complejidad espacial es la colección de todos los problemas que son decidibles por una máquina de Turing espacial no determinista.${\displaystyle {\mathsf {NSPACE}}(s(n))}$${\displaystyle O(s(n))}$

Clases de complejidad básica

Ver también: Lista de clases de complejidad

TODOS es la clase de todos los problemas de decisión . Muchas clases de complejidad importantes se definen delimitando el tiempo o el espacio utilizado por un algoritmo. A continuación se explican varias clases de complejidad importantes definidas de esta manera.

Clases de complejidad temporal

Artículo principal: complejidad del tiempo

Recuerde que la clase de complejidad del tiempo es la colección de todos los problemas que son decidibles por una máquina de Turing determinista en el tiempo y es la colección de todos los problemas que son decidibles por una máquina de Turing no determinista en el tiempo. Las clases de complejidad temporal a menudo se definen formalmente en términos de estas dos clases.${\displaystyle {\mathsf {DTIME}}(t(n))}$${\displaystyle O(t(n))}$${\displaystyle {\mathsf {NTIME}}(t(n))}$${\displaystyle O(t(n))}$

P y NP

Artículos principales: P (complejidad) y NP (complejidad)

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 pueden resolverse "rápida" o "eficientemente" por una computadora determinista, ya que la complejidad de tiempo para resolver un problema en P aumenta relativamente lentamente con el tamaño de entrada.

Una característica importante de la clase NP es que se puede definir 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 idioma está en NP si existe una máquina de Turing de tiempo polinomial determinista , denominada verificador, que toma como entrada una cadena y una cadena de certificado , y acepta si está en el idioma y rechaza si no está en el idioma. . Intuitivamente, el certificado actúa como prueba de que la entrada${\displaystyle w}$ ${\displaystyle c}$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$está en el idioma. Esta equivalencia no solo resalta una conexión fundamental entre el no determinismo y la verificabilidad de la solución, sino que también proporciona un método útil para probar que un idioma está en NP: simplemente identifique un certificado adecuado y demuestre que se puede verificar en tiempo polinomial.

Si bien puede parecer que hay una diferencia obvia entre la clase de problemas que se pueden resolver de manera eficiente y la clase de problemas que simplemente se pueden verificar 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 de P versus NP . Si bien se sabe que P NP (intuitivamente, las máquinas de Turing deterministas son solo una subclase de 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${\displaystyle \subseteq }$P . Si P = NP , entonces se deduce que el no determinismo no proporciona ningún poder computacional adicional sobre el determinismo con respecto a la capacidad de encontrar rápidamente una solución a un problema; es decir, ser capaz de explorar todas las ramas posibles de la computación proporciona como máximo una aceleración polinomial sobre la posibilidad de explorar una sola rama. Además, se seguiría que si existe una prueba para una instancia de problema cuya corrección se puede verificar rápidamente (es decir, si el problema está en NP ), entonces también existe un algoritmo que puede construir rápidamente esa prueba (es decir, el el problema está en P ).^[4] Sin embargo, la abrumadora mayoría de científicos informáticos cree que P NP , ^[5] y la mayoría de los esquemas criptográficos empleados en la actualidad se basan en la suposición de que P NP . ^[6]${\displaystyle \neq }$${\displaystyle \neq }$

EXPTIME y NEXPTIME

Artículos principales: EXPTIME y NEXPTIME

EXPTIME es la clase de problemas de decisión que puede resolver una máquina de Turing determinista en tiempo exponencial y NEXPTIME 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,

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

Clases de complejidad espacial

Artículo principal: Complejidad espacial

Recuerde que la clase de complejidad espacial es la colección de todos los problemas que son decidibles por una máquina de Turing determinista del espacio y es la colección de todos los problemas que son decidibles por una máquina de Turing no determinista del espacio. Las clases de complejidad espacial a menudo se definen formalmente en términos de estas dos clases. ${\displaystyle {\mathsf {DSPACE}}(s(n))}$${\displaystyle O(s(n))}$${\displaystyle {\mathsf {NSPACE}}(s(n))}$${\displaystyle O(s(n))}$

L y NL

Artículos principales: L (complejidad) y NL (complejidad)

Si bien es posible definir clases de complejidad de tiempo logarítmico , estas son clases extremadamente estrechas ya que los tiempos sublineales ni siquiera permiten que una máquina de Turing lea toda la entrada (porque ). ^[7] 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 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). ). ^[8]${\displaystyle \log n<n}$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.

Entonces, L se define como la clase de problemas que se pueden resolver en el espacio logarítmico en una máquina de Turing determinista y NL es la clase de problemas que se pueden resolver en el espacio logarítmico en una máquina de Turing no determinista. O más formalmente, ^[9]

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

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

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

PSPACE y NPSPACE

Artículo principal: PSPACE (complejidad)

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 P PSPACE , que se deduce intuitivamente del hecho de que, dado que escribir en una celda en la cinta de una máquina de Turing se define como una unidad de tiempo, una máquina de Turing que opera en tiempo polinomial solo puede escribir polinomialmente muchas celdas. Se sospecha que P es estrictamente menor que PSPACE , pero esto no ha sido probado.${\displaystyle \subseteq }$

EXPSPACE y NEXPSPACE

Artículo principal: EXPSPACE

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,

Error al analizar (MathML con respaldo SVG o PNG (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida ("La extensión matemática no se puede conectar a Restbase.") Desde el servidor "/ mathoid / local / v1 /" :): {\ 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 establece 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 cerrarse bajo negación , disyunción , conjunción o incluso bajo todas las operaciones booleanas . Además, también podrían cerrarse con una variedad de esquemas de cuantificación. P , por ejemplo, está cerrado en todas las operaciones booleanas y bajo cuantificación en dominios de tamaño polinomial (aunque probablemente no se cierre en dominios de tamaño exponencial). 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 y no la otra.

Cada clase X que no está cerrada bajo la negación tiene una clase de complemento co-X , que consiste en los complementos de los idiomas que figuran en X . De manera similar, se puede definir el cierre booleano de una clase, y así sucesivamente; sin embargo, esto se hace con menos frecuencia.

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 son. ^[10] 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 el tiempo. Ambos problemas están en P , sin embargo, 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 "que se pueden resolver de manera eficiente" utilizando algún polinomio más pequeño, como${\displaystyle t(n)=n}$${\displaystyle t(n)=n^{1000}}$${\displaystyle n^{2}}$, en lugar de todos los polinomios, lo que permite grandes discrepancias. Sin embargo, resulta que los polinomios son la clase más pequeña de funciones que contienen las funciones lineales que están cerradas bajo suma, multiplicación y composición. ^[10] Esto significa que los polinomios son la clase más pequeña que permite la composición de "algoritmos eficientes"; es decir, un algoritmo de tiempo polinomial que llama a una subrutina de tiempo polinomial todavía produce un algoritmo de tiempo polinomial. ^[11] Sin embargo, si se utilizara el límite, entonces componer un número constante de algoritmos "eficientes" podría resultar en un nuevo algoritmo que no es "eficiente". (Tenga en cuenta que la definición de P${\displaystyle n^{2}}$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 algoritmos conocidos con tiempos de ejecución exponenciales pequeños, es decir, con tiempos de ejecución donde está cerca de 1. ^[12] )${\displaystyle O(c^{n})}$${\displaystyle c}$

Dureza e integridad

Ver también: Reducción (complejidad)

Muchas clases de complejidad se definen utilizando el concepto de reducción . Una reducción es la transformación de un problema en otro problema. Capta la noción informal de que un problema es al menos tan difícil como otro problema. Por ejemplo, si un problema puede resolverse utilizando un algoritmo para , no es más difícil que , y decimos que se reduce a . Hay muchos tipos diferentes de reducciones, basadas en el método de reducción, como las reducciones de Cook , las reducciones de Karp y las reducciones de Levin , y el límite de la complejidad de las reducciones, como las reducciones de tiempo polinómico o las reducciones de espacio logarítmico.${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$ ${\displaystyle Y}$.

La reducción más utilizada es una reducción de tiempo polinomial. Esto significa que el proceso de reducción lleva un tiempo polinomial. Por ejemplo, el problema de elevar al cuadrado un número entero se puede reducir al problema de multiplicar dos números enteros. Esto significa que se puede usar un algoritmo para multiplicar dos números enteros para elevar al cuadrado un número entero. De hecho, esto se puede hacer dando la misma entrada a ambas entradas del algoritmo de multiplicación. Así vemos que el cuadrado no es más difícil que la multiplicación, ya que el cuadrado se puede reducir a una multiplicación.

Esto motiva 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 todos los problemas en C pueden reducirse a . Por lo tanto no hay problema en C es más difícil que , desde un algoritmo para nos permite resolver cualquier problema en C . Por supuesto, la noción de problemas difíciles depende del tipo de reducción que se utilice. Para clases de complejidad mayores que P , se usan comúnmente reducciones de tiempo polinómico. En particular, el conjunto de problemas que son difíciles para NP es el conjunto de problemas NP-difíciles .${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$

Si un problema se encuentra en C y es difícil para C , entonces se dice que es completa para el C . Esto significa que es el problema más difícil en C (dado que podría haber muchos problemas que son igualmente difíciles, se podría decir que es tan difícil como los problemas más difíciles en C ). Así, la clase de problemas NP -completos contiene los problemas más difíciles en NP , en el sentido de que son los que más probablemente no estén en P. Debido a que el problema P  =  NP no se resuelve, pudiendo reducir un NP conocido - problema completo, Π${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$₂ , a otro problema, Π ₁ , indicaría que no existe una solución de tiempo polinómico conocida para Π ₁ . Esto se debe a que una solución de tiempo polinomial para Π ₁ produciría una solución de tiempo polinomial para Π ₂ . De manera similar, debido a que todos los problemas NP se pueden reducir al conjunto, encontrar un problema NP completo que se pueda resolver en tiempo polinomial significaría que P  =  NP .

Relaciones entre clases de complejidad

Teorema de Savitch

Artículo principal: teorema de Savitch

El teorema de Savitch establece que PSPACE = NPSPACE y EXPSPACE = NEXPSPACE . Una cuestión central de la teoría de la complejidad es si el no determinismo agrega un poder significativo a un modelo computacional. Esto es fundamental para el problema abierto de P versus NP en el contexto del tiempo. El teorema de Savitch muestra que para el espacio, el no determinismo no agrega significativamente más poder, donde "significativo" significa la diferencia entre los requisitos de recursos polinomiales y superpolinomiales (o, para EXPSPACE, la diferencia entre exponencial y superexponencial). Por ejemplo, el teorema de Savitch demuestra que ningún problema que requiera espacio exponencial para una máquina de Turing determinista puede resolverse mediante una máquina de Turing espacial polinomial no determinista.

Teoremas de jerarquía

Artículos principales: Teorema de jerarquía temporal y Teorema de jerarquía espacial

Por definición de DTIME , se deduce que DTIME está contenido en DTIME 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 vienen dadas por los teoremas de la 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 la 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 (n^{k_{1}})}$${\displaystyle (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 la 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 la jerarquía de tiempo y espacio forman la base de la mayoría de los resultados de separación de clases de complejidad. Por ejemplo, el teorema de la jerarquía temporal establece que P está estrictamente contenido en EXPTIME , y el teorema de la 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 cálculo más utilizados, muchas clases de complejidad se definen en términos de otros modelos computacionales. En particular,

• Varias clases se definen utilizando máquinas probabilísticas de Turing , incluidas las clases BPP , PP , RP y ZPP
• Varias clases se definen 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.
• Varias clases se definen utilizando máquinas cuánticas de Turing , incluidas las clases BQP y QMA

Estos se explican con mayor detalle a continuación.

Cálculo aleatorio

Artículo principal: Computación aleatoria

Varias clases de complejidad importantes se definen utilizando la máquina probabilística de Turing , 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 al lanzamiento de una moneda. La aleatoriedad introducida en cada paso del cálculo introduce el potencial de error; es decir, las cadenas que la máquina de Turing debe aceptar pueden en algunas ocasiones ser rechazadas y las cadenas que la máquina de Turing debe rechazar pueden ser aceptadas en algunas ocasiones. Como resultado,las clases de complejidad basadas en la máquina probabilística de Turing se definen en gran parte en torno a la cantidad de error permitido. Formalmente, se definen utilizando una probabilidad de error.${\displaystyle \epsilon }$. Se dice que una máquina de Turing probabilística reconoce un lenguaje con probabilidad de error si:${\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 que no está en implica que${\displaystyle w}$${\displaystyle L}$${\displaystyle {\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon }$

Clases de complejidad importantes

Las 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 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 un poco más flexible es RP (tiempo polinomial aleatorio), que no mantiene ningún error para las cadenas que no están en el idioma, pero permite un error limitado para las cadenas en el idioma. Más formalmente, un lenguaje está en RP si hay una máquina de Turing probabilística de tiempo polinomial tal que si una cadena no está en el idioma, siempre se rechaza y si una cadena está en el idioma, entonces 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 permiten errores para cadenas en el idioma, pero sí para cadenas que no están en el idioma. En conjunto, las clases RP y co-RP${\displaystyle M}$${\displaystyle M}$${\displaystyle M}$abarcan todos los problemas que pueden resolverse mediante máquinas probabilísticas de Turing con error unilateral .

Si se aflojan aún más los requisitos de error para permitir el error de dos caras, 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 probabilidad de error menor que 1/3 (para ambas cadenas en el idioma y no en el idioma). 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 no resuelto en la informática sobre si P = BPP, lo que, de ser cierto, significaría que la aleatoriedad no aumenta el poder computacional de las computadoras, es decir, cualquier máquina de Turing probabilística podría ser simulada por una máquina de Turing determinista con una desaceleración polinómica como máximo.

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 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 el error cero y solo el error de un lado están todas contenidas dentro de la clase que permite el error de dos lados, y PP simplemente relaja la probabilidad de error de BPP . ZPP se relaciona con RP y co-RP de la siguiente manera: ZPP RP co-RP . Es decir, ZPP consiste exactamente en aquellos problemas que se encuentran tanto en RP como en co-RP . Intuitivamente, esto se deriva del hecho de que${\displaystyle =}$${\displaystyle \cap }$RP y co-RP solo permiten errores unilaterales: co-RP no permite errores para cadenas en el idioma y RP no permite errores para cadenas que no están en el idioma. Por lo tanto, si hay un problema tanto en RP como en co-RP , entonces no debe haber ningún error para las cadenas en el lenguaje y no en él (es decir, ningún error), que es exactamente la definición de ZPP .

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

Sistemas de prueba interactivos

Artículo principal: sistema de prueba interactivo

Varias clases de complejidad se definen utilizando sistemas de prueba interactivos . Las pruebas interactivas generalizan la definición de pruebas de la clase de complejidad NP y aportan conocimientos 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 el sistema acepta una cadena de entrada si el verificador decide aceptar la entrada sobre la base de los mensajes que ha recibido del probador. El probador${\displaystyle P}$${\displaystyle V}$${\displaystyle P}$tiene un poder computacional ilimitado mientras que el verificador tiene un poder computacional limitado (la definición estándar de sistemas de prueba interactivos define que el verificador está acotado polinomialmente). Sin embargo, el probador 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 prover "haciéndole" rondas sucesivas de preguntas, aceptando sólo si desarrolla un alto grado de confianza en que la cadena está en el idioma. ^[13]

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 de tiempo polinomial y el procedimiento se restringe a una ronda (es decir, el probador envía solo una prueba completa, generalmente conocida como el 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 demostraciones verificables en tiempo polinómico por una máquina de Turing determinista) hay un sistema de prueba en el que el la prueba es construida por un probador no mencionado y la máquina determinista de Turing es el verificador. Por esta razón, NP también se puede llamar dIP (prueba interactiva determinista), aunque rara vez se la denomina como tal.

Resulta que NP captura todo el poder de los sistemas de prueba interactivos con verificadores deterministas (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 los 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 cálculo aleatorio, los algoritmos probabilísticos introducen errores en el sistema, por lo que las clases de complejidad basadas en sistemas de prueba probabilística 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 polinomio-tiempo probabilístico y el sistema de prueba satisface dos propiedades: para un IP de idioma${\displaystyle (P,V)}$${\displaystyle V}$${\displaystyle L\in }$

1. (Completitud) una cadena en implica${\displaystyle w}$${\displaystyle L}$${\displaystyle \Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\geq {\tfrac {2}{3}}}$
2. (Solidez) una cuerda 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 de 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 sistemas de prueba interactivos utilizados por IP , el probador no pudo ver las monedas utilizadas por el verificador en su cálculo probabilístico; solo pudo ver los mensajes que el verificador produjo con estas monedas. Por esta razón, las monedas se denominan monedas privadas aleatorias . El sistema de prueba interactivo puede limitarse de modo que las monedas utilizadas por el verificador sean monedas públicas al azar ; es decir, el probador puede ver las monedas. Formalmente, AMse define como la clase de lenguajes con una prueba interactiva en la que el verificador envía una cadena aleatoria al prover, el prover responde con un mensaje y el verificador acepta o rechaza aplicando una función de tiempo polinomial determinista al mensaje del tirador de pruebas. 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, ocurre que para todo k 2, AM [k] = AM [2]. También es el caso de AM [k] IP [k].${\displaystyle \geq }$${\displaystyle \subseteq }$

Otras clases de complejidad definidas utilizando sistemas de prueba interactivos incluyen MIP (tiempo polinomial interactivo mutliprover) y QIP (tiempo polinomial interactivo cuántico).

Circuitos booleanos

Artículo principal: complejidad del circuito

Circuito Ejemplo Boolean el cálculo de la función booleana , con el ejemplo de entrada , y . Los nodos son puertas Y , los nodos son puertas OR y los nodos NO son puertas .${\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 de cálculo 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 el cálculo en teoría y el cálculo en la práctica, sino que también es un modelo natural para el cálculo no uniforme (cálculo en el que diferentes tamaños de entrada dentro del mismo problema utilizan diferentes algoritmos).

Formalmente, un circuito booleano es un gráfico acíclico dirigido en el que los bordes 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 bordes entrantes) y todos los vértices que no son de origen representan la lógica. puertas (generalmente las puertas Y , O y NO ). 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 está representado por la función booleana ; por ejemplo, en los bits de entrada , el bit de salida del circuito se representa matemáticamente como${\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})}$. Se dice que el circuito calcula la función booleana .${\displaystyle C}$${\displaystyle f_{C}}$

Cualquier circuito en particular tiene un número fijo de vértices de entrada, por lo que solo puede actuar sobre entradas de ese tamaño. Los lenguajes (las representaciones formales de los problemas de decisión ), sin embargo, 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 la máquina de Turing, en el que un lenguaje es completamente descrito por una sola máquina de Turing que puede actuar sobre cualquier tamaño de entrada). Por tanto, una lengua está representada 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 idioma si, para cada cadena , está en el idioma si y solo si${\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}$, 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 caracteres ) se evalúa como 1 cuando es su entrada.${\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 usando máquinas de Turing se describen en términos de complejidad de tiempo , las clases de complejidad de circuito se definen en términos de tamaño de circuito: el número de vértices en el circuito. La complejidad del tamaño de una familia de circuitos es la función , donde es el tamaño del circuito de . Las clases de funciones familiares se derivan naturalmente de esto; por ejemplo, una familia de circuitos de tamaño polinomial es una tal 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 existe una conexión natural entre la complejidad del circuito y la complejidad del tiempo. Intuitivamente, un lenguaje con poca complejidad de tiempo (es decir, requiere relativamente pocas operaciones secuenciales en una máquina de Turing), también tiene una pequeña complejidad de circuito (es decir, requiere relativamente pocas operaciones booleanas). Formalmente, se puede demostrar que si un lenguaje está en , donde está una función , entonces tiene complejidad de circuito . ^[14] De este hecho se deduce directamente que P P / poli${\displaystyle {\mathsf {DTIME}}(t(n))}$${\displaystyle t}$${\displaystyle t:\mathbb {N} \to \mathbb {N} }$${\displaystyle O(t^{2}(n))}$${\displaystyle \subseteq }$. 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, se da el caso de que la inclusión es adecuada, es decir, P P / poli (por ejemplo, hay algunos problemas indecidibles en P / poli ).${\displaystyle \subset }$

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 idioma en NP que no esté en P / poly , entonces P NP . ^[15] P / poly también es útil para investigar las propiedades de la jerarquía polinomial . Por ejemplo, si NP ⊆ P / poli , entonces PH colapsa a . Una descripción completa de las relaciones entre P / poli${\displaystyle \neq }$ ${\displaystyle \Sigma _{2}^{\mathsf {P}}}$y otras clases de complejidad están disponibles 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 se puede definir de manera equivalente como la clase de lenguajes reconocidos por una máquina de Turing de tiempo polinomial con una función de consejo acotada por polinomios .

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 al 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, las puertas pueden tener 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 se puede definir de manera equivalente como la clase de lenguajes que tienen algoritmos paralelos eficientes .

Computación cuántica

Esta sección necesita expansión . Puede ayudar agregando más . ( Abril de 2017 )

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

Otros tipos de problemas

Si bien la mayoría de las clases de complejidad son conjuntos de problemas de decisión , también hay una serie de clases de complejidad definidas en términos de otros tipos de problemas. En particular, existen 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.

Contando problemas

Artículo principal: problema de conteo (complejidad)

Un problema de conteo pregunta no solo si existe una solución (como con un problema de decisión ), sino también cuántas soluciones existen. ^[16] Por ejemplo, el problema de decisión pregunta si una gráfica en 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. ^[17] El resultado de un problema de conteo es, por tanto, un número, en contraste con el resultado de un problema de decisión, que es un simple sí / no (o aceptar / rechazar, 0/1 u otro esquema equivalente). ^[18]${\displaystyle CYCLE}$${\displaystyle G}$${\displaystyle \#CYCLE}$${\displaystyle G}$Entonces, mientras que los problemas de decisión se representan matemáticamente como lenguajes formales , los problemas de contar se representan matemáticamente como funciones : un problema de contar se formaliza como la función tal que, para una entrada , es el número de soluciones. Por ejemplo, en el problema, la entrada es un gráfico 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 CYCLE}$${\displaystyle G}$${\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 . ^[19]

Clases de complejidad importantes

Artículo principal: ♯P

#P (pronunciada "P aguda") es una clase de complejidad importante de problemas de conteo que se puede considerar como la versión de conteo de NP . ^[16] 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 aceptables en el árbol de cálculo de una máquina de Turing no determinista . Por tanto, #P se define formalmente de la siguiente manera:

#P es el conjunto de todas las funciones de manera que existe una máquina de Turing no determinista de tiempo polinomial tal que para todas , es igual al número de ramas aceptables en el árbol de cálculo de . ^[dieciséis]${\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 verificador (es decir, como un sistema de prueba interactivo ), también #P puede definirse de manera equivalente en términos de verificador. Recuerde que un problema de decisión está en NP si existe un certificado comprobable en tiempo polinomial para una instancia de problema dada, es decir, NP pregunta si existe una prueba de pertenencia para la entrada que pueda comprobarse en tiempo polinómico. La clase #P pregunta cuántos certificados existen. ^[16] En este contexto, #P se define de la siguiente manera:

# P es el conjunto de funciones tales que existe un polinomio de una máquina de Turing de tiempo polinómico y , llamado el verificador, tal que para cada , . ^[20] En otras palabras, es igual al tamaño del conjunto que contiene todos los certificados de tamaño polinomial.${\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)}$

Problemas de funcionamiento

Artículo principal: problema de función

Esta sección necesita expansión . Puede ayudar agregando más . ( Mayo de 2020 )

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 problema de cálculo en el que se espera una única salida (de una función total ) para cada entrada, pero la salida es más compleja que la de un problema de decisión . Para problemas de funcionamiento, la salida no es simplemente 'sí' o 'no'. La clase de complejidad FP es el conjunto de problemas de funciones que pueden ser resueltos por una máquina de Turing determinista en tiempo polinomial . ^[21]

Promesa problemas

Artículo principal: problema de la promesa

Esta sección necesita expansión . Puede ayudar agregando más . ( Mayo de 2020 )

Resumen de relaciones entre 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, el desglose en decidible e indecidible pertenece más al estudio de la teoría de la computabilidad , pero es útil para poner las clases de complejidad en perspectiva.

		Problema de decisión
Tipo 0 (recursivamente enumerable)				Indecidible
Decidible
EXPSPACE
NEXPTIME
EXPTIME
PSPACE
Tipo 1 (sensible al contexto)
		co-NP	BQP		notario público
			BPP
		PAG
	CAROLINA DEL NORTE
Tipo 2 (sin contexto)
Tipo 3 (regular)

Ver también

• Lista de clases de complejidad

Referencias

1. Arora y Barak p. 28
2. Sipser p. 48
3. Sipser p. 255
4. Aaronson, Scott (8 de enero de 2017). "P =? NP" . Coloquio electrónico sobre complejidad computacional . Instituto de Ciencias Weizmann. pag. 3.
5. "Columna de invitado: la tercera P =? NP Poll1" (PDF) .
6. Aaronson, Scott (8 de enero de 2017). "P =? NP" . Coloquio electrónico sobre complejidad computacional . Instituto de Ciencias Weizmann. pag. 4.
7. Sipser pág. 320
8. Sipser pág. 321
9. Sipser pág. 321
10. Aaronson, Scott (8 de enero de 2017). "P =? NP" . Coloquio electrónico sobre complejidad computacional . Instituto de Ciencias Weizmann. pag. 7.
11. Aaronson, Scott (14 de agosto de 2011). "Por qué los filósofos deberían preocuparse por la complejidad computacional" . Coloquio electrónico sobre complejidad computacional . Instituto de Ciencias Weizmann. pag. 5.
12. Aaronson, Scott (8 de enero de 2017). "P =? NP" . Coloquio electrónico sobre complejidad computacional . Instituto de Ciencias Weizmann. pag. 6.
13. Arora y Barak p. 144: "El verificador lleva a cabo un interrogatorio del probador, haciendo preguntas repetidamente y escuchando las respuestas del probador".
14. Sipser p. 355
15. Arora y Barak p. 286
16. Barak, Boaz (primavera de 2006). "Complejidad de contar" (PDF) . Ciencias de la Computación 522: Complejidad Computacional . Universidad de Princeton.
17. Arora, Sanjeev (primavera de 2003). "Clases de complejidad que tienen que ver con contar" . Ciencias de la Computación 522: Teoría de la Complejidad Computacional . Universidad de Princeton.
18. Arora y Barak p. 342
19. Arora y Barak p. 341-342
20. Arora y Barak p. 344
21. Arora y Barak p. 344

Bibliografía

• Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional: un enfoque moderno . Prensa de la Universidad de Cambridge. ISBN 978-0-521-42426-4.
• Sipser, Michael (2006). Introducción a la Teoría de la Computación (2ª ed.). EE.UU .: Thomson Course Technology. ISBN 978-0-534-95097-2.

Lectura adicional

• The Complexity Zoo : una enorme lista de clases de complejidad, una referencia para los 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 clases de complejidad y cómo encajan.
• Michael Garey y David S. Johnson : Computadoras e intratabilidad: una guía para la teoría de NP-Completeness. Nueva York: WH Freeman & Co., 1979. La referencia estándar sobre problemas NP-Complete: una categoría importante de problemas cuyas soluciones parecen requerir un tiempo de cálculo imprácticamente largo.