Clase de complejidad

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En la teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas computacionales "de complejidad relacionada basada en 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 determinista de Turing en tiempo polinomial. Sin embargo, existen muchas clases de complejidad definidas en términos de otros tipos de problemas (por ejemplo, problemas de conteo y problemas de funciones) y que utilizan otros modelos de computación (por ejemplo, máquinas 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: 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 en informática se refiere a si P es igual a NP. Las relaciones entre clases a menudo responden preguntas sobre la naturaleza fundamental de la computación. El problema P versus NP, por ejemplo, está directamente relacionado con preguntas sobre si el no determinismo agrega alguna potencia computacional a las computadoras y si los problemas que tienen soluciones cuya corrección se puede verificar rápidamente pueden También se solucionará 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 sólo una pregunta que puede resolverse por un algoritmo. Por ejemplo, "es el número natural ${displaystyle n}$ ¿Primer?" es un problema computacional. Un problema computacional está representado matemáticamente como el conjunto de respuestas al problema. En el ejemplo de la primalidad, el problema (llamarlo ${displaystyle {textttt {fnK}}$ ) está representado por el conjunto de todos los números naturales que son primo: ${displaystyle {textttt {f}=\nnnfnfn} }}}}}$ . En la teoría de la computación, estas respuestas están representadas como cuerdas; por ejemplo, en el ejemplo de la primalidad los números naturales podrían ser representados como cadenas de bits que representan números binarios. Por esta razón, los problemas computacionales a menudo se denominan idiomas sinónimos, ya que las cadenas de bits representan lenguajes formales (un concepto tomado de los lingüísticos); por ejemplo, diciendo que los ${displaystyle {textttt {fnK}}$ el problema es en la clase de complejidad NP es equivalente a decir que el idioma ${displaystyle {textttt {fnK}}$ está dentro NP.

Problemas de decisión

Los problemas más comúnmente analizados en la ciencia informática teórica son los problemas de decisión, los tipos de problemas que pueden plantearse como sí, sin preguntas. El ejemplo de primalidad arriba, por ejemplo, es un ejemplo de un problema de decisión ya que puede ser representado por el sí – ninguna pregunta "es el número natural ${displaystyle n}$ "Primer". En términos de la teoría de la computación, un problema de decisión está representado como el conjunto de cadenas de entrada que un ordenador que ejecuta un algoritmo correcto respondería "sí" a. En el ejemplo de la primalidad, ${displaystyle {textttt {fnK}}$ es el conjunto de cadenas que representan números naturales que, cuando entran en un ordenador que ejecuta un algoritmo que prueba correctamente para la primalidad, el algoritmo responde "sí, este número es primo". Este formato "sí-no" es a menudo equivalentemente declarado como "acept-reject"; es decir, un algoritmo "acepta" una cadena de entrada si la respuesta al problema de decisión es "sí" y "rechace" si la respuesta es "no".

Si bien algunos problemas no pueden expresarse fácilmente como problemas de decisión, abarcan una amplia gama de problemas computacionales. 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 (ver apartado "Otro tipo de problemas").

Modelos computacionales

Para concretar la noción de "computadora", en la informática teórica los problemas se analizan en el contexto de un modelo computacional. Los modelos computacionales hacen exactas las nociones de recursos computacionales como "tiempo" y "memoria". En la teoría de la complejidad computacional, las clases de complejidad se ocupan de los requisitos de recursos inherentes de 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. El "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 cada algoritmo puede representarse como una máquina de Turing.

Mecánicamente, una máquina de Turing (TM) manipula símbolos (generalmente restringidos a los bits 0 y 1 para proporcionar una conexión intuitiva con las computadoras de la vida real) contenidos en una tira de cinta infinitamente larga. 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, por ejemplo, “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 se puede definir en términos de una máquina Turing como el conjunto de cadenas de entrada que una máquina Turing en particular acepta. Por ejemplo, el problema de la primalidad ${displaystyle {textttt {fnK}}$ de arriba es el conjunto de cuerdas (representando números naturales) que una máquina Turing ejecuta un algoritmo que prueba correctamente para primalidad acepta. A Turing machine is said to reconocer un lenguaje (reconoce que "problema" y "lengua" son en gran medida sinónimos en la teoría de computabilidad y complejidad) si acepta todas las entradas que están en el idioma y se dice a decidir a language if it additionally rejects all inputs that are not in the language (certain inputs may cause a Turing machine to run forever, so decidability places the additional limitt over recognizability that the Turing machine must halt on all inputs). Una máquina de Turing que "solves" un problema es generalmente significa uno que decide el idioma.

Las máquinas de Turing permiten nociones intuitivas del "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

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" acciones futuras. una sucursal que acepte (si alguna 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 un "aceptar" condició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. 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 el NTM utiliza en cualquier rama de su cálculo. 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 problemas computacionales por sus necesidades de recursos. Para ello, los problemas computacionales se diferencian por límites superiores en la cantidad máxima de recursos que el algoritmo más eficiente requiere para resolverlos. Más específicamente, las clases de complejidad se ocupan de las tasa de crecimiento en 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 se necesita para resolver problemas en la clase de complejidad P crece a un ritmo polinomio a medida que aumenta el tamaño de la entrada, que es comparativamente lento en comparación con los problemas de la clase de complejidad exponencial EXPTIME (o más exactamente, para problemas en EXPTIME que están fuera de P, desde ${displaystyle {Mathsf}subseteq {fnMithsf {}}}$ ).

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 del tiempo de un algoritmo con respecto al modelo de máquina Turing es el número de pasos que toma para una máquina Turing para ejecutar un algoritmo en un tamaño de entrada dado. Formalmente, la complejidad del tiempo para un algoritmo implementado con una máquina Turing ${displaystyle M}$ se define como la función ${displaystyle # Mathbb # {N} to mathbb {N}$ , donde ${displaystyle t_{M}(n)}$ es el número máximo de pasos que ${displaystyle M}$ toma cualquier entrada de longitud ${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 máquina Turing es el número de células en la cinta de la máquina 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 Turing ${displaystyle M}$ se define como la función ${displaystyle "Mathbb" {N}$ , donde ${displaystyle s_{M}(n)}$ es el número máximo de células que ${displaystyle M}$ usos en cualquier entrada de longitud ${displaystyle n}$ .

Clases de complejidad básica

Definiciones básicas

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

La clase de complejidad del tiempo ${displaystyle {mathsf {}(t(n)}$ es el conjunto de todos los problemas que se deciden por un ${displaystyle O(t(n)}$ tiempo determinista máquina Turing.
La clase de complejidad del tiempo ${displaystyle {mathsf {NTIME}(t(n)}$ es el conjunto de todos los problemas que se deciden por un ${displaystyle O(t(n)}$ tiempo máquina Turing no determinista.
La clase de complejidad espacial ${displaystyle {mathsf {}(s(n)}$ es el conjunto de todos los problemas que se deciden por un ${displaystyle O(s(n)}$ espacio determinista máquina Turing.
La clase de complejidad espacial ${displaystyle {mathsf {NSPACE}(s(n)}$ es el conjunto de todos los problemas que se deciden por un ${displaystyle O(s(n)}$ espacio no fijo Máquina de Turing.

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 polinomial y NP es la clase de problemas que pueden resolverse con una máquina de Turing no determinista en tiempo polinomial. O más formalmente,

{displaystyle {Mathsf}=bigcup _{kin mathbb {N} {fn} {fn} {fn}} {fn}} {fn}} {fn}}} {fn}}} {fn}}}} {fn} {fn} {fn}}}} {fn}}}} {fn}} {fn}}}}}}}}} {

{displaystyle {Mathsf}=bigcup _{kin mathbb {N} {fn} {fn} {fn}} {fn}} {fn}} {fn}} {fn} {fn}}} {fn}}}} {fn}} {fn}}} {fn}}} {fn}}}} {fn}}}}}}}}} {

A menudo se dice que

P es la clase de problemas que se pueden resolver "rápidamente" o "eficientemente" por 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 equivalentemente como la clase de problemas cuyas soluciones son verificable por una máquina de Turing determinista en tiempo polinomio. Es decir, un lenguaje está dentro NP si existe determinista tiempo polinomio Máquina de Turing, conocida como el verificador, que toma como entrada una cadena ${displaystyle w}$ y una cadena de certificado de tamaño polinomio ${displaystyle c}$ , y acepta ${displaystyle w}$ si ${displaystyle w}$ está en el idioma y rechaza ${displaystyle w}$ si ${displaystyle w}$ no está en el lenguaje. Intuitivamente, el certificado actúa como prueba de que la entrada ${displaystyle w}$ está en el idioma. Formally:

NP es la clase de idiomas

{displaystyle L.

para el cual existe un determinista polinomio-tiempo Máquina de tortuga

{displaystyle M}

y un polinomio

{displaystyle p}

tal que para todos

{displaystyle win {0,1} {}}} {}}}

{displaystyle w}

está dentro

{displaystyle L.

si existe

{displaystyle cin {0,1}} {p(Sobrevivir)}}

tales que

{displaystyle M(w,c)}

acepta.

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 polinómico.

El problema P versus NP

Aunque podría parecer una diferencia obvia entre la clase de problemas que son eficientemente solvables y la clase de problemas cuyas soluciones son meramente verificables de manera eficiente, P y NP están en el centro de uno de los problemas más famosos sin resolver en la ciencia de la computadora: el problema P versus NP. Aunque se sabe que P ${displaystyle subseteq }$ NP (intuitivamente, las máquinas Turing deterministas son sólo una subclase de máquinas Turing no deterministas que no hacen uso de su no determinismo; o bajo la definición verificadora, P es la clase de problemas cuyos verificadores de tiempo polinomio sólo necesitan recibir la cadena vacía como su certificado), no se sabe si NP es estrictamente mayor que P. Si P=NP, entonces sigue que el nodeterminismo proporciona no 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 a la mayoría una aceleración polinomio sobre poder explorar sólo una rama. Además, seguiría que si existe una prueba para una instancia de problema y que la prueba se puede comprobar rápidamente para la corrección (es decir, si el problema está en NP), entonces también existe un algoritmo que puede rápidamente construcción esa prueba (es decir, el problema está en P). Sin embargo, la mayoría abrumadora de científicos informáticos creen que P ${displaystyle neq }$ NP, y la mayoría de los esquemas criptográficos empleados hoy dependen de la suposición de que P ${displaystyle neq }$ NP.

EXPTIME y NEXPTIME

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

{displaystyle {mathsf {}=bigcup _{kin mathbb {N}{mathsf {DTIME}(2^{n^{k}) }

{displaystyle {Mathsf {NEXPTIME}=bigcup _{kin mathbb {N}{mathsf {NTIME}(2^{n^{k}) }

EXPTIME es un superset estricto P y NEXPTIME es un superset estricto NP. It is further the case that EXPTIME ${displaystyle subseteq }$ NEXPTIME. No se sabe si esto es apropiado, pero si P=NP entonces EXPTIME debe ser igual NEXPTIME.

Clases de complejidad espacial

L y Holanda

Aunque es posible definir las 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 toda la entrada (porque ${displaystyle log n maden}$ ). 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). En el modelo de dos cintas Turing máquina, una cinta es la cinta de entrada, que es sólo 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 Turing realiza computaciones. La complejidad espacial de la máquina Turing se mide como el número de células que se utilizan en la cinta de trabajo.

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 determinista de Turing 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,

{displaystyle {mathsf {}={mathsf {fnMicrosoft Sans Serif} {gnMicrosoft Sans Serif}} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}} {f}}}} {f} {fnMicrosoft Sans}}}}fnMicrosoft Sansigually}}}f}}}}}}f}fnMicrosoft SanscnMicrosoft SanscnMicrosoft Sans}}f}}}}}}}}}}}}}}}f}}}}fnMissssssssssssssssssssssssssstodastelo sé lo siento lo siento lo siento como si!

{displaystyle {mathsf {}={mathsf {NSPACE}}(log n)}

Se sabe que ${displaystyle {Mathsf {}subseteq {Mathsf {f}subseteq {Mathsf {}}}}$ . Sin embargo, no se sabe si alguna de estas relaciones es adecuada.

PSPACIO y NPSPACE

Las clases de complejidad PSPACE y NPSPACE son las análogas 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 {fnK}=bigcup _{kin mathbb {N} {fn} {fn} {fn}} {fn}} {fn}}} {fn}} {fn}}} {fn}}}} {fn} {fn}} {fn}}}} {fn}} {fn}}} {fn}}}}}}}}}} {

{displaystyle {mathsf {fnK}=bigcup _{kin mathbb {N} {fn} {fn} {fn}} {fn}} {fn}}} {fn}} {fn}}} {fn}}} {fn}} {fn}}}}}} {

Aunque no se sabe si P=NPEl teorema de Savitch mostró que PSPACE=NPSPACE. También se sabe que P ${displaystyle subseteq }$ PSPACE, que sigue intuitivamente del hecho de que, desde la escritura a una célula en 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 polinomio sólo puede escribir a polinomial muchas células. Se sospecha que P es estrictamente menor que PSPACE, pero esto no ha sido probado.

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 {fnMicrosoft}=bigcup _{kin mathbb {N}{mathsf {DSPACE}(2^{n^{k}) }

{displaystyle {Mathsf {NEXPSPACE}=bigcup _{kin 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. superconjunto 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á cerrado bajo negación tiene una clase de complemento co-X, que consta de los complementos de los idiomas contenidos en X (i.e. co-X= ${displaystyle ################################################################################################################################################################################################################################################################ {L}in }$ X ${displaystyle}$ ). co-NP, por ejemplo, es una clase de complejidad de complemento importante, y se sienta en el centro del problema sin resolver sobre si co-NP=NP.

Las propiedades de cierre son una de las razones clave que muchas clases de complejidad se definen de la manera que son. Tomemos, por ejemplo, un problema que se puede resolver en ${displaystyle O(n)}$ tiempo (es decir, en tiempo lineal) y uno que puede ser resuelto en, al mejor, ${displaystyle O(n^{1000})}$ 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 el tamaño de entrada aumenta. Se podría preguntar si sería mejor definir la clase de problemas "eficientemente solvable" usando algún límite polinomio más pequeño, como ${displaystyle O(n^{3}}$ , en lugar de todos los polinomios, que permite tales grandes discrepancias. Resulta, sin embargo, que el conjunto de todos los polinomios es la clase más pequeña de funciones que contienen las funciones lineales que también se cierran bajo adición, multiplicación y composición (por ejemplo, ${displaystyle O(n^{3})circ O(n^{2})=O(n^{6}$ , que es un polinomio pero ${displaystyle O(n^{6})$ ). Dado que nos gustaría componer un algoritmo eficiente con otro algoritmo eficiente para ser considerado eficiente, los polinomios son la clase más pequeña que asegura la composición de " algoritmos eficientes". (Nota que la definición de P es también útil porque, empíricamente, casi todos los problemas en P que son prácticamente útiles tienen tiempo de funcionamiento polinomio de bajo orden, y casi todos los problemas fuera de P que son prácticamente útiles no tienen ningún algoritmo conocido con pequeños tiempos de ejecución exponencial, es decir, con ${displaystyle O(c^{n}}$ horas de funcionamiento donde ${displaystyle c}$ está cerca de 1.)

Reducciones

Muchas clases de complejidad se definen utilizando el concepto de un Reducción. Una reducción es una transformación de un problema en otro problema, es decir, una reducción toma insumos de un problema y los transforma en insumos de otro problema. Por ejemplo, usted puede reducir la base ordinaria-10 adición ${displaystyle x+y)$ a la adición base-2 mediante la transformación ${displaystyle x}$ y ${displaystyle y}$ a su notación base-2 (por ejemplo 5+7 se convierte en 101+111). Formally, un problema ${displaystyle X}$ reduce a un problema ${displaystyle Sí.$ si existe una función ${displaystyle f}$ por cada uno ${displaystyle xin Sigma ^{*}$ , ${displaystyle xin X}$ si ${displaystyle f(x)in Y}$ .

Generalmente, se utilizan reducciones para captar la noción de un problema siendo al menos tan difícil como otro problema. Por lo tanto estamos generalmente interesados en utilizar una reducción de tiempo polinomio, ya que cualquier problema ${displaystyle X}$ que puede reducirse eficientemente a otro problema ${displaystyle Sí.$ no es más difícil que ${displaystyle Sí.$ . Formally, un problema ${displaystyle X}$ es polinomial-time reducible a un problema ${displaystyle Sí.$ si existe polinomial-time función computable ${displaystyle p}$ tal que para todos ${displaystyle xin Sigma ^{*}$ , ${displaystyle xin X}$ si ${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 un problema siendo duro para una clase de complejidad. Un problema ${displaystyle X}$ es difícil para una clase de problemas C si todos los problemas C se puede reducir el tiempo polinomio a ${displaystyle X}$ . Así no hay problema C es más difícil que ${displaystyle X}$ , desde un algoritmo ${displaystyle X}$ nos permite resolver cualquier problema en C con mayor desaceleración polinómica. De particular importancia, el conjunto de problemas que son difíciles para NP se llama el conjunto de NP-hard problemas.

Integridad

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

De particular importancia es la clase de problemas NP-completos: los problemas más difíciles en NP. Debido a que todos los problemas en NP se pueden reducir en tiempo polinómico a problemas NPcompletos, encontrar un problema NPcompleto que pueda resolverse en polinomios el tiempo significaría que P = NP.

Relaciones entre clases de complejidad

Teorema de Savitch

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

{displaystyle {mathsf {NSPACE}left(fleft(nright)right)subseteq {mathsf {DSPACE}left(fleft(nright)^{2}right). }

Los corolarios importantes del teorema de Savitch son que PSPACE = NPSPACE (ya que el cuadrado de un polinomio sigue siendo un polinomio) y EXPSPACE b> = NEXPSPACE (ya que el cuadrado de un exponencial sigue siendo 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 el espacio exponencial, una máquina de Turing determinista también puede resolverlo en el espacio exponencial.

Teoremas de jerarquía

Por definición DTIME, sigue que ${displaystyle {mathsf {cH00} {cH00}} {cH00}}$ figura en ${displaystyle {mathsf {cH00} {cH00}} {cH00}}$ si ${displaystyle k_{1}leq k_{2}$ , desde ${displaystyle O(n^{k_{1}})subseteq O(n^{k_{2}}}}$ si ${displaystyle k_{1}leq k_{2}$ . Sin embargo, esta definición no indica si esta inclusión es estricta. Para requisitos de tiempo y espacio, las condiciones bajo las cuales la inclusión es estricta se dan por el tiempo y los teoremas de jerarquía espacial, respectivamente. Se llaman teoremas jerárquicos porque inducen una jerarquía adecuada en las clases definidas limitando los recursos respectivos. Los teoremas jerarquizados permiten hacer declaraciones cuantitativas sobre cuánto más tiempo o espacio es necesario para aumentar el número de problemas que se pueden resolver.

El teorema de la jerarquía temporal establece que

{bign]}subsetneq {mathsf {big}{big (}f(n)cdot log ^{2}(f(n)} {big)}}} {big}}} {bign)}}}}}}}}

El teorema de la jerarquía espacial establece que

{bign]} {bign]}subsetneq {mathsf {f} {big}{big (}f(n)cdot log(f(n)}{big)}}}}}}} {big}}}}}}} {bign)}}

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 < b>PSPACIO.

Otros modelos de computación

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

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

Estos se explican con mayor detalle a continuación.

Cálculo aleatorio

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 en lugar de seguir una única función de transición (un conjunto de reglas para cómo proceder a cada paso de la computación) que 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 a una moneda flip. La aleatoriedad introducida en cada paso de la computación introduce el potencial de error; es decir, cadenas que la máquina de Turing está destinada a aceptar pueden en algunas ocasiones ser rechazadas y cadenas que la máquina de Turing está destinada a 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 alrededor de la cantidad de error que se permite. Formally, se definen usando una probabilidad de error ${displaystyle epsilon }$ . Una máquina de Turing probabilística ${displaystyle M}$ se dice que reconocer un idioma ${displaystyle L.$ con probabilidad de error ${displaystyle epsilon }$ si:

una cuerda ${displaystyle w}$ dentro ${displaystyle L.$ implica que ${displaystyle {text{Pr}[M{text{ accepts }w]geq 1-epsilon }$
una cuerda ${displaystyle w}$ no en ${displaystyle L.$ implica que ${displaystyle {text{fnK}[M{text{ rejects }w]gq 1-epsilon }$

Clases de complejidad importantes

Las clases fundamentales de complejidad de tiempo aleatorio son ZPP, RP, co-RP, BPP y < b>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 exige ningún error.

Una clase más suelta es RP (tiempo polinomio aleatorio), que no mantiene ningún error para cadenas no en el idioma, pero permite el error ligado para cadenas en el idioma. Más formalmente, un idioma está en RP si hay una máquina de Turing polinomial probabilista ${displaystyle M}$ tal que si una cadena no está en el idioma entonces ${displaystyle M}$ siempre rechaza y si una cadena está en el idioma entonces ${displaystyle M}$ acepta con una probabilidad al menos 1/2. La clase co-RP se define de forma similar excepto los roles son volteados: el error no se permite para cadenas en el idioma, pero se permite para cadenas no en el idioma. Juntos, las clases RP y co-RP abarca todos los problemas que pueden resolverse por las máquinas probabilísticas de Turing con un error unilateral.

Aflojar aún más los requisitos de error para permitir el error bilateral produce la clase BPP (tiempo polinomial 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 error. probabilidad 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 sin resolver en informática sobre si P=BPP, 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 simularse mediante 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 eficientemente es el 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 cuerdas.

ZPP, RP y co-RP son todos los subconjuntos de BPP, que a su vez es un subconjunto de PP. La razón de esto es intuitiva: las clases que permiten un error cero y sólo errores unilaterales están contenidas en la clase que permite un error de dos caras, y PP simplemente relaja la probabilidad de error BPP. ZPP relacionados con RP y co-RP de la siguiente manera: ${displaystyle {textsf {ZPP}={textsf {}cap {textsf {}}}$ . Eso es, ZPP consiste exactamente en esos problemas que están en ambos RP y co-RP. Intuitivamente, esto se deriva del hecho de que RP y co-RP permite sólo un error unilateral: co-RP no permite errores para cadenas en el idioma y RP no permite el error de cadenas no en el idioma. Por lo tanto, si un problema está en ambos RP y co-RP, entonces no debe haber error para las cuerdas en y no en el idioma (es decir, ningún error), que es exactamente la definición ZPP.

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 brindan información sobre criptografía, algoritmos de aproximación y verificación formal.

Los sistemas de pruebas interactivas son máquinas abstractas que modelan la computación como el intercambio de mensajes entre dos partes: un prover ${displaystyle P}$ y un verificador ${displaystyle V}$ . 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 proveror ${displaystyle P}$ tiene poder computacional ilimitado mientras que el verificador ha atado el poder computacional (la definición estándar de los sistemas de prueba interactiva define el verificador a estar ligado polinomialmente). El proverbio, sin embargo, no es confiable (esto impide que todos los idiomas sean trivialmente reconocidos por el sistema de pruebas al tener el proverbio sin límites computacionalmente resuelto para si una cadena está en un idioma y luego enviar un confiable "Sí" o "NO" al verificador), por lo que el verificador debe llevar a cabo una "interrogación" del proverso por "levantándola" suces rondas de preguntas, aceptando un alto grado de confianza sólo si desarrolla.

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 está restringido a una ronda (es decir, el probador envía sólo un prueba única y completa (normalmente denominada certificado) al verificador). Dicho de otra manera, en la definición de la clase NP (el conjunto de problemas de decisión para los cuales las instancias del problema, cuando la respuesta es "SÍ", tienen pruebas verificables en tiempo polinómico mediante una máquina determinista de Turing) es un sistema de prueba en el que 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 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 (polynomial-time) 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 mensajería entre el proveror y el verificador. Los sistemas de prueba interactivos que proporcionan mayor poder computacional sobre las clases de complejidad estándar requieren así probabilístico verificadores, lo que significa que las preguntas del verificador al probador se computan usando algoritmos probabilísticos. Como se señala en la sección anterior sobre computación aleatorizada, algoritmos probabilísticos introducen error en el sistema, por lo que las clases de complejidad basadas en sistemas de prueba probabilístico se definen en términos de probabilidad de error ${displaystyle epsilon }$ .

La clase de complejidad más general que surge de esta caracterización es la clase IP (tiempo polinomio interactivo), que es la clase de todos los problemas solvable por un sistema de prueba interactiva ${displaystyle (P,V)}$ , donde ${displaystyle V}$ es el tiempo polinomio probabilístico y el sistema de prueba satisface dos propiedades: para un idioma ${displaystyle Lin {Mathsf {IP}}$

(Completa) una cadena ${displaystyle w}$ dentro ${displaystyle L.$ implicación ${displaystyle Pr[V{text{ accepts }w{text{ after interacting with }P]geq {tfrac {2}{3}}$
Una cuerda ${displaystyle w}$ no en ${displaystyle L.$ implicación ${displaystyle Pr[V{text{ accepts }w{text{ after interacting with }P]leq {tfrac {1}{3}}$

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

Modificación del protocolo IP produce otra clase de complejidad importante: AM (Protocolo Arthur-Merlin). En la definición de sistemas de prueba interactivos utilizados por IP, el proveror no pudo ver las monedas utilizadas por el verificador en su computación probabilística - sólo pudo ver los mensajes que el verificador producido con estas monedas. Por esta razón, las monedas se llaman monedas privadas al azar. El sistema de prueba interactiva se puede restringir para que las monedas utilizadas por el verificador sean monedas públicas al azar; es decir, el proveror es capaz de ver las monedas. Formalmente, AM se define como la clase de idiomas con una prueba interactiva en la que el verificador envía una cadena aleatoria al proveror, el proverbio responde con un mensaje, y el verificador acepta o rechaza aplicando una función determinista de tiempo polinomio al mensaje del proverbio. AM se puede generalizar AM[k], donde k es el número de mensajes intercambiados (también en la forma generalizada el estándar AM definida anteriormente AM[2]). Sin embargo, es el caso que para todos ${displaystyle kgeq 2}$ , AM[k]=AM[2]. Es también el caso de que ${displaystyle {mathsf}[k]subseteq {mathsf {}[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

Un modelo de computación alternativo a la máquina de Turing es el circuito booleano, un modelo simplificado de los circuitos digitales utilizados en las computadoras modernas. Este modelo no solo proporciona una conexión intuitiva entre la computación 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 ${displaystyle C}$ es un gráfico acíclico dirigido en el que los bordes representan alambres (que llevan los valores de bits 0 y 1), los bits de entrada están representados por los vértices de origen (vertices sin bordes entrantes), y todos los vértices no fuente representan las puertas lógicas (generalmente las puertas AND, OR y NO). Una puerta lógica es designada la puerta de salida, y representa el final de la computación. El comportamiento de entrada/salida de un circuito ${displaystyle C}$ con ${displaystyle n}$ variables de entrada está representada por la función Boolean ${displaystyle ¿Qué?$ ; por ejemplo, en bits de entrada ${displaystyle x_{1},x_{2},...,x_{n}$ , el bit de salida ${displaystyle b}$ del circuito está representado matemáticamente como ${displaystyle b=f_{C}(x_{1},x_{2},...,x_{n}$ . El circuito ${displaystyle C}$ se dice que computador la función booleana ${displaystyle F_{C}$ .

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

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

Clases de complejidad importantes

La clase de complejidad P/pobre es el conjunto de idiomas que son decidables por las familias de circuitos de tamaño polinomio. Resulta que hay una conexión natural entre la complejidad del circuito y la complejidad del tiempo. Intuitivamente, un lenguaje con pequeña complejidad del tiempo (es decir, requiere relativamente pocas operaciones secuenciales en una máquina de Turing), también tiene una pequeña complejidad del circuito (es decir, requiere relativamente pocas operaciones booleanas). Formally, se puede demostrar que si un idioma está en ${displaystyle {mathsf {}(t(n)}$ , donde ${displaystyle t}$ es una función ${displaystyle t:mathbb {N} to mathbb {N}$ , entonces tiene la complejidad del circuito ${displaystyle O(t^{2}(n)}$ . De este hecho se desprende directamente que ${displaystyle {Mathsf} Subset {P/poly}}$ . En otras palabras, cualquier problema que pueda resolverse en el tiempo polinomio por una máquina de Turing determinista también puede ser resuelto por una familia de circuitos de tamaño polinomio. Es más, el caso de que la inclusión sea adecuada, es decir, ${displaystyle {textsf {}subsetneq {textsf {P/poly}}$ (por ejemplo, hay algunos problemas indecibles que están en P/pobre).

P/pobre tiene una serie de propiedades que lo hacen muy útil en el estudio de las relaciones entre las clases de complejidad. En particular, es útil investigar problemas relacionados con P versus NP. Por ejemplo, si hay algún idioma en NP que no está P/pobre, entonces ${displaystyle {Mathsf {}neq {Mathsf}}$ . P/pobre también es útil para investigar las propiedades de la jerarquía polinómica. Por ejemplo, si NP ⊆ P/pobre, entonces PH colapsos a ${displaystyle "Sigma"$ . Una descripción completa de las relaciones entre P/pobre y otras clases de complejidad están disponibles en "Importancia de P/poly". P/pobre También es útil en el estudio general de las propiedades de las máquinas de Turing, ya que la clase puede ser equivalentemente definida como la clase de idiomas reconocida por una máquina de Turing polinomio-time con una función de asesoramiento polinomio.

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 polinomial sino también a tener profundidad polilogarítmica. La clase AC se define de manera similar a NC, sin embargo, se permite que las compuertas tengan una entrada ilimitada (es decir, las compuertas AND y OR se pueden aplicar a más de dos bits).). NC es una clase notable porque puede definirse de manera equivalente como la clase de lenguajes que tienen algoritmos paralelos eficientes.

Computación cuántica

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

Otro tipo 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

A Contando problemas pide no sólo si existe una solución (como con un problema de decisión), pero pregunta cuántos existen soluciones. Por ejemplo, el problema de la decisión ${displaystyle {textttt {}}}$ preguntas si un gráfico particular ${displaystyle G.$ tiene un ciclo simple (la respuesta es un simple sí/no); el problema de conteo correspondiente ${displaystyle #{textttt {CYCLE}}$ (pronunciado "ciclo sharp") pregunta cuántos ciclos simples ${displaystyle G.$ Sí. El producto a un problema contable es por lo tanto un número, a diferencia de la salida para un problema de decisión, que es un simple sí/no (o aceptar/rechazar, 0/1, u otro esquema equivalente).

Por lo tanto, mientras que los problemas de decisión se representan matemáticamente como idiomas formales, los problemas contables se representan matemáticamente como funciones: un problema contable se formaliza como la función ${displaystyle f:{0,1}{*}to mathbb {N}$ tal que para cada entrada ${displaystyle win {0,1} {}}} {}}}$ , ${displaystyle f(w)}$ es el número de soluciones. Por ejemplo, en el ${displaystyle #{textttt {CYCLE}}$ problema, la entrada es un gráfico ${displaystyle Gin {0,1}{*}$ (un gráfico representado como una cadena de bits) y ${displaystyle f(G)}$ es el número de ciclos simples en ${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.

Clases de complejidad importantes

#P (pronunciado "P sostenido") es una clase importante de problemas de conteo que se puede considerar como la versión de conteo de NP. 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. #P se define formalmente de la siguiente manera:

#P es el conjunto de todas las funciones

{displaystyle f:{0,1}{*}to mathbb {N}

tal que hay un tiempo polinomio no determinista Máquina de tortuga

{displaystyle M}

tal que para todos

{displaystyle win {0,1} {}}} {}}}

{displaystyle f(w)}

iguala el número de ramas aceptadas en

{displaystyle M}

's árbol de computación en

{displaystyle w}

Y así como NP se puede definir tanto en términos de no determinismo como en términos de un verificador (es decir, como un sistema de prueba interactivo), también se puede definir #P. definido 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 comprobar en tiempo polinómico. La clase #P pregunta cuántos certificados de este tipo existen. En este contexto, #P se define de la siguiente manera:

#P es el conjunto de funciones

{displaystyle f:{0,1}{*}to mathbb {N}

tal que exista un polinomio

{displaystyle p:mathbb {N} to mathbb {N}

y una máquina de Turing polinomio

{displaystyle V}

(el verificador), tal que para cada

{displaystyle win {0,1} {}}} {}}}

{fnMicrosoft Sans Serif}{big{}cin {0,1}^{p(aprendiz)}:V(w,c)=1{big {fnK}}

. En otras palabras,

{displaystyle f(w)}

iguala el tamaño del conjunto que contiene todos los certificados de tamaño polinomio para

{displaystyle w}

Problemas de funcionamiento

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

{displaystyle Rsubseteq Sigma ^{*}times Sigma ^{*}

Un algoritmo resuelve ${displaystyle f}$ si por cada entrada ${displaystyle x}$ tal que exista ${displaystyle y}$ satisfacción ${displaystyle (x,y)in R}$ , el algoritmo produce uno de tales ${displaystyle y}$ . Esta es otra forma de decir que ${displaystyle f}$ es una función y el algoritmo resuelve ${displaystyle f(x)}$ para todos ${displaystyle xin 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. 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. 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).

Así como FP es el problema de función equivalente a P, FNP es el problema de función equivalente a NP. Es importante destacar que FP=FNP si y sólo si P=NP.

Problemas de promesa

Problemas de promesa son una generalización de los problemas de decisión en los que se garantiza la entrada a un problema ("prometido") a ser de un subconjunto particular de todos los insumos posibles. Recuerda eso con un problema de decisión ${displaystyle Lsubseteq{0,1}{*}}}$ , un algoritmo ${displaystyle M}$ para ${displaystyle L.$ debe actuar (correctamente) cada uno ${displaystyle win {0,1} {}}} {}}}$ . Un problema de promesa afloja el requisito de entrada en ${displaystyle M}$ restringiendo la entrada a algún subconjunto ${displaystyle {0,1}} {}}} {fnMicrosoft Sans Serif}$ .

Específicamente, un problema de promesa se define como un par de conjuntos sin intersección ${displaystyle (Pi _{text{ACCEPT}},Pi _{text{REJECT}}}$ , donde:

${displaystyle Pi _{text{ACCEPT}subseteq {0,1}{*}}$ es el conjunto de todos los insumos que son aceptados.
${displaystyle Pi _{text{REJECT}subseteq {0,1}{*}}$ es el conjunto de todos los insumos que son rechazados.

La entrada a un algoritmo ${displaystyle M}$ para un problema de promesa ${displaystyle (Pi _{text{ACCEPT}},Pi _{text{REJECT}}}$ Así es. ${displaystyle Pi _{text{ACCEPT}cup "Pi"$ , que se llama el promesa. Pendientes en ${displaystyle Pi _{text{ACCEPT}cup "Pi"$ se dice que satisfacer la promesa. Por definición, ${displaystyle Pi _{text{ACCEPT}}$ y ${displaystyle "Pi"$ debe ser descomunal, es decir. ${displaystyle Pi _{text{ACCEPT}cap Pi _{text{REJECT}=emptyset }$ .

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

Los problemas de promesa hacen una formulación más natural de muchos problemas computacionales. Por ejemplo, un problema computacional podría ser algo como "dar un gráfico planar, determinar si o no..." Esto se dice a menudo como un problema de decisión, donde se supone que hay algún esquema de traducción que toma cada uno cuerda ${displaystyle sin {0,1} {}} {}}}$ 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 es un gráfico plano.

Relación con las clases de complejidad

Los problemas de promesa proporcionan una definición alternativa para las clases de complejidad estándar de los problemas de decisión. P, por ejemplo, se puede definir como un problema de promesa:

P es la clase de problemas de promesa que son solvables en el tiempo polinomio determinista. Es decir, el problema de la promesa

{displaystyle (Pi _{text{ACCEPT}},Pi _{text{REJECT}}}

está dentro P si existe un algoritmo de tiempo polinomio

{displaystyle M}

tal que:

Por todos ${displaystyle xin Pi _{text{ACCEPT}},M(x)=1}$
Para siempre ${displaystyle xin Pi _{text{REJECT}},M(x)=0}$

Clases de problemas de decisión, es decir, clases de problemas definidos como idiomas formales, que se traducen naturalmente en problemas de promesa, donde un idioma ${displaystyle L.$ en la clase es simplemente ${displaystyle L= Pi...$ y ${displaystyle "Pi"$ es implícita ${displaystyle {0,1}{*}/ Pi...$ .

Formular 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).

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 decidibles e indecidibles pertenece más al estudio de la teoría de la computabilidad, pero es útil para poner las clases de complejidad en perspectiva.

Problema de decisión

Tipo 0 (Recursivamente enumerable)

Undecidable

Decidible

EXPSPACE

NEXPTIME

EXPTIME

PSPACE

Tipo 1 (Contexto sensible)

co-NP

BQP

BPP

Tipo 2 (Contexto libre)

Tipo 3 (regular)