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 basada en recursos ". ^[1] 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 computación y un recurso limitado como el tiempo o la memoria . En particular, la mayoría de las clases de complejidad consisten en problemas de decisión que se pueden resolver con una máquina de Turing y se diferencian por sus requisitos de tiempo o espacio (memoria). Por ejemplo, la clase P es el conjunto de problemas de decisión que puede resolver una máquina determinista de Turing en tiempo polinómico . 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 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 existen jerarquías generales de clases de complejidad; por ejemplo, se sabe que varias clases fundamentales de complejidad temporal y espacial se relacionan entre sí de la siguiente manera: L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE (donde ⊆ denota la relación de subconjunto ). Sin embargo, aún no se conocen muchas relaciones; por ejemplo, uno de los problemas abiertos más famosos en informática se refiere a si P es igual a NP . Las relaciones entre clases a menudo responden preguntas sobre la naturaleza fundamental de la computación. El problema P versus NP , por ejemplo, está directamente relacionado con cuestiones de si el no determinismo añade algún poder computacional a las computadoras y si los problemas que tienen soluciones cuya corrección se puede verificar rápidamente también pueden resolverse rápidamente.

Fondo

Las clases de complejidad son conjuntos de problemas computacionales relacionados . Se definen en términos de la dificultad computacional de resolver los problemas 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 resolverse mediante una máquina de Turing con recursos temporales o espaciales limitados . Por ejemplo, la clase de complejidad P se define como el conjunto de problemas de decisión que pueden resolverse mediante una máquina de Turing determinista en tiempo polinomial .

Problemas computacionales

Intuitivamente, un problema computacional es solo una cuestión que puede resolverse mediante un algoritmo . Por ejemplo, "¿el número natural es primo ?" es un problema computacional. Un problema computacional se representa matemáticamente como el conjunto de respuestas al problema. En el ejemplo de primalidad, el problema (llámelo ) 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 de 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 equivale 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 tiene sólo dos salidas posibles, sí o no (alternativamente, 1 o 0) en cualquier entrada.

Los problemas más comúnmente analizados en informática teórica son los problemas de decisión (el tipo 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 representarse mediante la pregunta de sí o 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 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 de "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". ${\displaystyle n}$ ${\displaystyle {\texttt {PRIME}}}$

Si bien algunos problemas no pueden expresarse fácilmente como problemas de decisión, 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 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 los problemas se analizan en el contexto de un modelo computacional . Los modelos computacionales precisan 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 fueron diseñadas. Al proporcionar representaciones matemáticas abstractas de las computadoras, los modelos computacionales abstraen complejidades superfluas del mundo real (como 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 computación"), la máquina de Turing se utiliza para definir la mayoría de las clases de complejidad básicas. Con la máquina de Turing, en lugar de utilizar unidades de tiempo estándar como el segundo (que 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 elementos elementales. pasos que sigue 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 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

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 comúnmente 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 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 todo 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. El TM puede leer y escribir, uno a la vez, usando un cabezal de cinta. El funcionamiento está totalmente 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 sólo con la cadena de entrada en su cinta y deja espacios en blanco en el resto. El TM acepta la entrada si ingresa a un estado de aceptación designado y rechaza la entrada si ingresa a 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 le 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 particular. Por ejemplo, el problema de primalidad visto anteriormente 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 entradas que no están en el lenguaje (ciertas entradas pueden hacer que una máquina de Turing se ejecute para siempre, 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 aquella que decide el lenguaje. ${\displaystyle {\texttt {PRIME}}}$

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

Máquinas de Turing no deterministas

Una comparación de computación determinista y no determinista. Si alguna 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 desde un estado determinado y "elegir" una rama que acepte (si alguna lo acepta). Es decir, mientras que un DTM debe seguir solo una rama de cálculo, un NTM puede imaginarse como un árbol de cálculo, que se ramifica en muchas rutas computacionales posibles en cada paso (ver imagen). Si al menos una rama del árbol se detiene con una condición de "aceptación", entonces el 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 pretenden 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 utiliza el NTM 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.

Las MDT pueden verse como un caso especial de MNA que no hacen uso del poder del no determinismo. Por tanto, todos los cálculos que puede realizar un DTM también pueden realizarse mediante 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 tanto, los dos son equivalentes en términos de computabilidad. Sin embargo, simular un NTM con un DTM a menudo requiere más tiempo y/o recursos de memoria; Como se verá, cuán significativa es esta desaceleración para ciertas clases de problemas computacionales es una cuestión importante en la teoría de la complejidad computacional.

Límites de recursos

Las clases de complejidad agrupan los problemas computacionales según sus requisitos de recursos. Para ello, los problemas computacionales se diferencian por límites superiores de la cantidad máxima de recursos que necesita el algoritmo más eficiente para resolverlos. Más específicamente, las clases de complejidad se ocupan de la tasa de crecimiento de los recursos necesarios para resolver problemas computacionales particulares a medida que aumenta el tamaño de la entrada. Por ejemplo, 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 cual 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}}}$

Tenga en cuenta que el estudio de las clases de complejidad tiene como objetivo principal 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, 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 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 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 requiere 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 informáticos teóricos 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 del tiempo. Por ejemplo, ¿la función de complejidad del tiempo es un polinomio ? ¿ Una función logarítmica ? ¿ Una función exponencial ? ¿U 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 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 determinado. 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 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 basicas

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

• La clase de complejidad temporal es el conjunto de todos los problemas que se resuelven 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 resuelven 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 resuelve 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 resuelve una máquina de Turing espacial no determinista. ${\displaystyle {\mathsf {NSPACE}}(s(n))}$ ${\displaystyle O(s(n))}$

Clases de complejidad del tiempo.

P y NP

P es la clase de problemas que pueden resolverse con una máquina de Turing determinista en tiempo polinómico y NP es la clase de problemas que pueden resolverse con una máquina de Turing no determinista en tiempo polinómico. 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á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 mediante una máquina determinista de Turing en tiempo polinomial. Es decir, un lenguaje está en NP si existe una máquina de Turing de tiempo polinómico determinista , denominada verificador, que toma como entrada una cadena y una cadena de certificado de tamaño polinómico , acepta si está en el idioma y rechaza si no lo está . en el idioma. Intuitivamente, el certificado actúa como prueba de que la entrada está en el idioma. Formalmente: ^[5] ${\displaystyle w}$ ${\displaystyle c}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle w}$

NP es la clase de lenguajes para los cuales existe una máquina de Turing determinista de tiempo polinomial y un polinomio tal que para todos , está en si y solo 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 del 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 : simplemente identifique un certificado adecuado y demuestre que se puede verificar en tiempo polinomial.

El problema P versus NP

Si bien podría parecer que hay una diferencia obvia entre la clase de problemas que se pueden resolver eficientemente y la clase de problemas cuyas soluciones simplemente se pueden verificar de manera eficiente, P y NP están en realidad en el centro de uno de los problemas no resueltos más famosos de la informática: el problema 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 según la definición del verificador, P es la clase de problemas cuyos verificadores de tiempo polinómicos solo necesitan recibir la cadena vacía como su certificado), no se sabe si NP es estrictamente mayor que P . Si P = NP , entonces se deduce que el no determinismo no proporciona poder computacional adicional sobre el determinismo con respecto a la capacidad de encontrar rápidamente una solución a un problema; es decir, poder explorar todas las ramas posibles de la computación proporciona como máximo una aceleración polinómica respecto de poder explorar solo una rama. Además, se seguiría que si existe una prueba para una instancia de problema y se puede verificar rápidamente si esa prueba 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 inmensa mayoría de los científicos informáticos cree que P NP , ^[7] y la mayoría de los esquemas criptográficos empleados hoy en día se basan en la suposición de que P NP . ^[8] ${\displaystyle \subseteq }$ ${\displaystyle \neq }$ ${\displaystyle \neq }$

EXPTIME y PRÓXIMO

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

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

Clases de complejidad espacial

L y NL

Si bien es posible definir clases de complejidad de tiempo 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 un número significativo de problemas que pueden resolverse 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 ). ^[10] En el modelo de máquina de Turing de dos cintas, una cinta es la cinta de entrada, que es de sólo lectura. La otra es la cinta de trabajo, que permite tanto leer como escribir y es la cinta sobre la que la máquina de Turing realiza 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. ${\displaystyle \log n<n}$

L (a veces ampliado a LOGSPACE ) se define entonces como la clase de problemas que se pueden resolver en un espacio logarítmico en una máquina de Turing determinista y NL (a veces ampliado a NLOGSPACE ) es la clase de problemas que se pueden resolver en un 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 PSPACE , 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 tomar una unidad de tiempo, una máquina de Turing que opera en tiempo polinómico sólo puede escribir en muchas celdas polinomiales. Se sospecha que P es estrictamente menor que PSPACE , pero esto no ha sido probado. ${\displaystyle \subseteq }$

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 cerrarse bajo negación , disyunción , conjunción o incluso bajo todas las operaciones booleanas . Además, también podrían cerrarse según diversos esquemas de cuantificación. P , por ejemplo, está cerrado en todas las operaciones booleanas y en la cuantificación en 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 negación tiene una clase de complemento co-X , que consta de los complementos de los lenguajes contenidos en X (es decir, co-X = X ). co-NP , por ejemplo, es una clase importante de complejidad del complemento y se encuentra en el centro del problema no resuelto sobre si co-NP = NP . ${\displaystyle \{L|{\overline {L}}\in }$ ${\displaystyle \}}$

Las propiedades de cierre son una de las razones clave por las que muchas clases de complejidad se definen como 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 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 la entrada. Uno podría preguntarse si sería mejor definir la clase de problemas "resolubles eficientemente" utilizando algún límite polinomial 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 funciones lineales y que también está cerrada en suma, multiplicación y composición (por ejemplo, , que es un polinomio pero ). ^[11] Dado que nos gustaría que componer un algoritmo eficiente con otro algoritmo eficiente aún se considere eficiente, los polinomios son la clase más pequeña que garantiza la composición de "algoritmos eficientes". ^[12] (Tenga en cuenta 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 tiempos de ejecución polinomiales de orden bajo, y casi todos los problemas fuera de P que son prácticamente útiles no tienen ningún tiempo de ejecución polinómico de bajo orden. algoritmos conocidos con tiempos de ejecución exponenciales pequeños, es decir, con tiempos de ejecución cercanos a 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})}$ ${\displaystyle c}$

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 de base 10 a una suma de base 2 transformando y a su notación de base 2 (por ejemplo, 5+7 se convierte en 101+111). Formalmente, un problema se reduce a problema si existe una función tal que para cada , si y sólo 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}$

Generalmente, las reducciones se utilizan para captar la noción de que un problema es al menos tan difícil como otro problema. Por lo tanto, generalmente estamos interesados ​​en utilizar una reducción de tiempo polinomial, ya que cualquier problema que pueda reducirse eficientemente a otro problema no es más difícil que . Formalmente, un problema es reducible en tiempo polinomial a un problema si existe una función computable en tiempo polinomial tal que para todos , si y sólo 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 comunes son las reducciones de Cook , las reducciones de Karp y las reducciones de Levin , y pueden variar según los límites de 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 denomina 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 está en C , entonces se dice que está completo para C. Esto significa que es el problema más difícil en C (dado que puede haber muchos problemas que son 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 reducirse en tiempo polinomial a problemas NP completos, encontrar un problema NP completo que pueda resolverse en tiempo polinomial significaría que P  =  NP .

Relaciones entre clases de complejidad

teorema de savitch

El teorema de Savitch establece la relación entre 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 responden a preguntas fundamentales sobre el poder del no determinismo en comparación con el determinismo. Específicamente, el teorema de Savitch muestra que cualquier problema que una máquina de Turing no determinista pueda resolver en el espacio polinomial, una máquina de Turing determinista también puede resolverlo en el espacio polinomial. De manera similar, cualquier problema que una máquina de Turing no determinista pueda resolver en un espacio exponencial, una máquina de Turing determinista también puede resolverlo en un espacio exponencial.

Teoremas de jerarquía

Por definición de DTIME , se deduce que está contenido en if , desde if . Sin embargo, esta definición no da ninguna indicación sobre 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 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 más 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 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 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 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 computación 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 mediante 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.

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 probabilística de Turing 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 la posibilidad 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 en algunas ocasiones aceptarse. 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 mediante una probabilidad de error . Se dice que una máquina probabilística de Turing reconoce un lenguaje con probabilidad de error si: ${\displaystyle \epsilon }$ ${\displaystyle M}$ ${\displaystyle L}$ ${\displaystyle \epsilon }$

1. una cadena implica que ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle {\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon }$
2. una cadena que no está 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 de tiempo aleatorio son ZPP , RP , co-RP , BPP y PP .

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

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

Si se flexibilizan aún más los requisitos de error para permitir el error bilateral se obtiene la clase BPP (tiempo polinómico probabilístico de error acotado), la clase de problemas que se pueden resolver en tiempo polinómico mediante una máquina probabilística de Turing con una probabilidad de error inferior a 1/3 (para ambas cadenas). en el idioma y no en el idioma). BPP es la más relevante en la práctica de las clases de complejidad probabilística: 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 ciencias de la computación 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 probabilística de Turing podría ser simulada por una máquina determinista de Turing con como máximo una desaceleración polinómica.

La clase más amplia de problemas probabilísticos que se pueden resolver eficientemente es PP (tiempo polinómico probabilístico), el conjunto de lenguajes que se pueden resolver mediante una máquina probabilística de Turing en tiempo polinómico con una probabilidad de error inferior a 1/2 para todas las cadenas.

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

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

Sistemas de prueba interactivos

Varias clases de complejidad se definen mediante 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 en función 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 sistemas de prueba interactivos define que el verificador tiene un límite polinomial en el tiempo). El probador, sin embargo, no es confiable (esto evita que el sistema de prueba reconozca trivialmente todos los idiomas 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 "formulándole" rondas sucesivas de preguntas, aceptando sólo 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 se limita a ser una máquina de Turing de tiempo polinómico determinista y el procedimiento se restringe a una ronda (es decir, el probador envía sólo una prueba única y completa, normalmente denominada prueba completa). 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 polinómico mediante una máquina determinista de Turing) es un sistema de prueba en el que la La prueba es construida por un demostrador no mencionado y la máquina determinista de Turing es el verificador. Por esta razón, NP también puede denominarse 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 única ronda de mensajes entre los probador y verificador. Los sistemas de prueba interactivos que proporcionan 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í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 polinómico interactivo), que es la clase de todos los problemas que pueden resolverse mediante un sistema de prueba interactivo , donde es el tiempo polinómico probabilístico y el sistema de prueba satisface dos propiedades: para un idioma ${\displaystyle (P,V)}$ ${\displaystyle V}$ ${\displaystyle L\in {\mathsf {IP}}}$

1. (Integridad) 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 cadena que no está en 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 de espacio polinómico, 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 este motivo, 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 públicas aleatorias ; 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 determinista de tiempo polinomial al mensaje del prover. 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, se da el caso de que para todo , AM [ k ] = AM [2]. También se da el caso de que . ${\displaystyle k\geq 2}$ ${\displaystyle {\mathsf {AM}}[k]\subseteq {\mathsf {IP}}[k]}$

Otras clases de complejidad definidas utilizando sistemas de prueba interactivos incluyen MIP (tiempo polinómico interactivo multiprover) y QIP (tiempo polinómico interactivo cuántico).

circuitos booleanos

Ejemplo de circuito booleano que calcula la función booleana , con entrada de ejemplo , y . Los nodos son puertas Y , los nodos son puertas O 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 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 (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 bits 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 lógica. puertas (generalmente las puertas AND , OR y NOT ). Una puerta lógica se denomina 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 . 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 en particular tiene un número fijo de vértices de entrada, por lo que sólo 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 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 se describe completamente mediante una única máquina de Turing que puede actuar sobre cualquier tamaño de entrada). Una lengua está así representada por una familia de circuitos . Una familia de circuitos es una lista infinita de circuitos , donde hay 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 , donde está 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 ) se evalúa como 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 utilizando máquinas de Turing se describen en términos de complejidad temporal , las clases de complejidad del circuito se definen en términos de tamaño del circuito: el número de vértices del circuito. La complejidad del tamaño de una familia de circuitos es la función , donde es el tamaño del circuito . Las conocidas clases de funciones se derivan naturalmente de esto; por ejemplo, una familia de circuitos de tamaño polinómico 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 existe una conexión natural entre la complejidad del circuito y la complejidad del tiempo. Intuitivamente, un lenguaje con pequeña 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 hay una función , entonces tiene complejidad de circuito . ^[16] De este hecho se desprende directamente que . 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 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 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 . ^[17] P/poly también es útil para investigar las propiedades de la jerarquía polinomial . 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 un polinomio . ${\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 sólo 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 del camino dirigido más largo desde un nodo de entrada hasta el nodo de salida. La clase NC es el conjunto de lenguajes que pueden resolverse mediante familias de circuitos que están restringidas no solo a tener tamaño polinómico 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 una entrada en abanico ilimitada (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 , de importancia clave en la ciencia de la información cuántica , se definen mediante máquinas cuánticas de Turing .

Otros tipos de problemas

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

problemas de conteo

Un problema de conteo pregunta no sólo si existe una solución (como ocurre con un problema de decisión ), sino también 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] El resultado de un problema de conteo es, por lo 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). ^[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 , está 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 se puede considerar 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á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 tales que existe una máquina de Turing no determinista de tiempo polinomial tal que, para todas , es igual al número de ramas aceptantes en el árbol de cálculo de . ^[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 de un verificador (es decir, como un sistema de prueba interactivo ), también #P puede definirse de manera equivalente en términos de un verificador. Recuerde que un problema de decisión está en NP si existe un certificado verificable en tiempo polinomial para una instancia de problema determinada; es decir, NP pregunta si existe una prueba de membresía (un certificado) para la entrada cuya corrección se puede verificar en polinomio. tiempo. 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 en tiempo polinómico (el verificador), tal que para cada , . ^[23] En otras palabras, es igual al tamaño del conjunto que contiene todos los certificados de tamaño polinómico 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 funciones . 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 entre 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 exista una satisfacción , el algoritmo produce una tal . Esta es sólo otra forma de decir que es una función y el algoritmo resuelve para todos . ${\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 de complejidad de función importante es FP , la clase de funciones que se pueden resolver de manera eficiente. ^[23] Más específicamente, FP es el conjunto de problemas de funciones que pueden resolverse mediante una máquina de Turing determinista en tiempo polinomial . ^[23] FP puede considerarse como el problema de función equivalente a P. Es importante destacar que FP proporciona una idea tanto de los problemas de conteo como de P versus NP . Si #P = FP , entonces las funciones que determinan el número de certificados para problemas en NP se pueden resolver de manera eficiente. Y dado que calcular el número de certificados es al menos tan difícil como determinar si existe un certificado, se debe seguir que si #P = FP entonces P = NP (no se sabe si esto es válido 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 sólo 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. Recuerde que en un problema de decisión , un algoritmo debe actuar (correctamente) en cada . Un problema de promesa afloja el requisito de entrada al restringir la entrada a algún 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 cruzan , 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 , lo que se denomina promesa . Se dice que las cadenas cumplen la promesa . ^[25] Por definición, y debe ser disjunto, 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 problemas de promesa con promesa trivial . Por lo tanto, en los problemas de decisión es más sencillo definir simplemente el problema como único (con ser implícitamente ), lo que a lo largo de esta página se indica 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 constituyen una formulación más natural de muchos problemas computacionales. Por ejemplo, un problema computacional podría ser algo así como "dado un gráfico plano , determinar si..." ^[26] Esto a menudo se plantea como un problema de decisión, donde se supone que hay algún esquema de traducción que toma cada cadena a un gráfico plano. Sin embargo, es más sencillo definir esto como un problema de promesa en el que se promete que la entrada será un gráfico plano. ${\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, puede definirse como un problema de promesa: ^[27]

P es la clase de problemas de promesa que se pueden resolver en tiempo polinomial determinista. Es decir, el problema de la 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 simple 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ásica como P como problemas de promesa proporciona poca información adicional sobre su naturaleza. Sin embargo, hay algunas clases de complejidad para las cuales formularlas como problemas prometedores ha resultado útil para los informáticos. Los problemas de promesas, por ejemplo, han jugado un papel clave en el estudio del SZK (conocimiento estadístico cero). ^[28]

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.

Ver 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 torneado lea entradas de tamaño , invariablemente llegará a 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, pag. 48, 150.
4. Sipser 2006, pag. 255.
5. Aaronson 2017, pag. 12.
6. Aaronson 2017, pag. 3.
7. Gasarch 2019.
8. Aaronson 2017, pag. 4.
9. Sipser 2006, pag. 320.
10. Sipser 2006, pág. 321.
11. Aaronson 2017, pág. 7.
12. Aaronson 2017, pag. 5.
13. Aaronson 2017, pag. 6.
14. Lee 2014.
15. Arora y Barak 2009, pág. 144.
16. Sipser 2006, pag. 355.
17. Arora y Barak 2009, pág. 286.
18. Por ahora 1997.
19. Arora 2003.
20. Arora y Barak 2009, pág. 342.
21. Arora y Barak 2009, pág. 341–342.
22. Barak 2006.
23. Arora y Barak 2009, p. 344.
24. Rico 2008, pag. 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 Weizmann de Ciencias. Archivado desde el original el 17 de junio de 2020.
• Arora, Sanjeev ; Barac, Booz (2009). Complejidad computacional: un enfoque moderno . Prensa de la Universidad de Cambridge. 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 que tienen que ver con contar". 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) . Informática 522: Complejidad computacional . Universidad de Princeton . Archivado desde el original el 3 de abril de 2021.
• Fortnow, Lance (1997). "Contar la complejidad" (PDF) . En Hemaspaandra, Lane A.; Selman, Alan L. (eds.). Retrospectiva de la Teoría de la Complejidad II . Saltador. págs. 81-106. ISBN 9780387949734. Archivado desde el original (PDF) el 18 de junio de 2022.
• Gasarch, Guillermo I. (2019). "Columna de invitados: ¿La tercera P =? Encuesta NP" (PDF) . Universidad de Maryland . Archivado (PDF) desde el original el 2 de noviembre de 2021.
• Goldreich, Oded (2006). "Sobre los problemas de las promesas: una encuesta" (PDF) . En Goldreich, Oded; Rosenberg, Arnold L.; Selman, Alen L. (eds.). Informática Teórica. Apuntes de conferencias sobre informática, vol 3895 (PDF) . Apuntes de conferencias sobre informática. vol. 3895. Saltador. págs. 254–290. doi :10.1007/11685654_12. ISBN 978-3-540-32881-0. Archivado (PDF) desde el 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). "Conferencia 16" (PDF) . CSE431: Introducción a la Teoría de la Computación . Universidad de Washington . Archivado (PDF) desde el original el 29 de noviembre de 2021 . Consultado el 5 de octubre de 2022 .
• Rico, Elaine (2008). Autómatas, Computabilidad y Complejidad: Teoría y Aplicaciones (PDF) . Prentice Hall . ISBN 978-0132288064. Archivado (PDF) desde el original el 21 de enero de 2022.
• Sipser, Michael (2006). Introducción a la Teoría de la Computación (PDF) (2ª ed.). Estados Unidos: Tecnología del curso Thomson. ISBN 0-534-95097-3. Archivado desde el 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) desde el original el 18 de junio de 2022.

Otras lecturas

• The Complexity Zoo 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 clases de complejidad y cómo encajan entre sí.
• Michael Garey y David S. Johnson : Computadoras e intratabilidad: una guía para la teoría de la NP-completitud. 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 calcularse.