Clases de Complejidad, parte III

En la entrada anterior se describió como se define una clase de complejidad, en términos de maquinas de Turing y lenguajes recordaremos unas definiciones que ampliaremos.

Dada una función ƒ(n), se consideran las clases de complejidad siguientes:

• Clase TIME(ƒ(n)) es el conjunto de lenguajes L tales que una máquina de Turing determinista decide en tiempo ƒ(n).
  
• Clase NTIME(ƒ(n)) es el conjunto de lenguajes L tales que una máquina de Turing no determinista decide en tiempo ƒ(n).
  
• Clase SPACE(ƒ(n)) es el conjunto de lenguajes L tales que una máquina de Turing determinista decide usando un espacio ƒ(n).
  
• Clase NSPACE(ƒ(n)) es el conjunto de lenguajes L tales que una máquina de Turing no determinista decide usando un espacio ƒ(n).
  

Ahora bien en base a la familia de funciones parametrizadas por un entero k>0, que acotan el recurso, en esta caso el tiempo, podemos definir las siguientes clases:

• Clase P es el conjunto de lenguajes L tales que una máquina de Turing determinista decide en tiempo polinomial TIME(ƒ(n^k)).
  P = ∪_k>0 TIME(ƒ(n^k)).
  
• Clase NP es el conjunto de lenguajes L tales que una máquina de Turing no determinista decide en tiempo polinomial NTIME(ƒ(n^k)).
  NP = ∪_k>0 NTIME(ƒ(n^k)).
  
• Clase EXP es el conjunto de lenguajes L tales que una máquina de Turing determinista decide en tiempo polinomial TIME(ƒ(2^nk)).
  
• Clase NEXP es el conjunto de lenguajes L tales que una máquina de Turing no determinista decide en tiempo polinomial TIME(ƒ(2^nk)).
  

Ahora definiremos las clases en base a la familia de funciones el espacio:

• Clase PSPACE es el conjunto de lenguajes L tales que una máquina de Turing determinista decide usando un espacio SPACE(ƒ(n^k)).
  P = ∪_k>0 TIME(ƒ(n^k)).
  
• Clase NPSPACE es el conjunto de lenguajes L tales que una máquina de Turing no determinista decide usando un espacio NSPACE(ƒ(n^k)).
  NP = ∪_k>0 NSPACE(ƒ(n^k)).
  
• Clase L es el conjunto de lenguajes L tales que una máquina de Turing determinista decide en tiempo polinomial SPACE(ƒ(log n).
  
• Clase NL es el conjunto de lenguajes L tales que una máquina de Turing no determinista decide en tiempo polinomial NSPACE(ƒ(log n)).
  

Hay una serie de inclusiones entre las distintas clases de complejidad:
SPACE(ƒ(n)) ⊆ NSPACE(ƒ(n)),
TIME(ƒ(n)) ⊆ NTIME(ƒ(n)),

Se han dedicado muchos esfuerzos a estudiar las relaciones entre clases de complejidad diferentes, y todavía quedan problemas abiertos como P = NP? o P ≠ NP?.

Se tiene claro P ⊆ NP, pero no se ha conseguido aún demostrar ni que P = NP ni lo contrario, que P ≠ NP. Para demostrar la primera, P = NP, sería necesario demostrar que todo problema de NP puede resolverse con una máquina de Turing determinista en tiempo polinomial. Y para demostrar la segunda, P ≠ NP, habría que encontrar un problema NP que no esté en P, un problema para el que exista una maquina de Turing no determinista de complejidad en tiempo polinomial para el que nunca pueda encontrarse uno determinista de la misma complejidad.

Algo que puede causar ruido es se ha demostrado que PSPACE = NPSPACE, un resultado que suguiere fuertemente que el no determinismo es menos poderoso con respecto al espacio que con respecto al tiempo. Con esta información podemos hacer las siguientes inclusiones:

L ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE.

Ahora bien a continuación definiremos dos conceptos muy importantes en la teoría de la complejidad: reducción y completitud.

Reducciones.

Las clases de complejidad contiene un conjunto infinito de lenguajes, por ejemplo la clase NP contiene problemas como TSP, SAT, CLIQUE, entre otros. No todos los problemas en la misma clase son igualmente dificiles, para establecer un orden de problemas de acuerdo a su dificulta, se proponen las reducciones. Un problema A es por lo menos tan difícil como otro problema B si existe una reducción del problema B al problema A.

Decimos que el problema B se reduce al problema A si existe una transformación R tal que, por cada entrada x de B, produce una entrada equivalente y de A, es decir y = R(x) . El término equivalente quiere decir que la respuesta a R(x) considerada como entrada para B es una respuesta correcta a y considerada como entrada para A. En otras palabaras, para resolver B por la entrada x sólo hay que construir R(x) y resolver A. Si contamos entonces con un algoritmo para el problema A y un algoritmo para construir R(x) la combinacion de ambos nos da un algoritmo para resolver B.

Aqui es importante que la reducción es facil de construir, en pocas palabras, las reducciones tambien se clasifican según los recusos que se usen, por ejemplo las reducciones de Cook permite que R(x) sean computadas por una máquina de Turing en tiempo polinomial y reducciones de espacio logarítmico. Poniendolo en terminos de lenguajes, se tiene:

Un lenguaje L es reducible a un lenguaje L′ , denotado por L ≤_L L′ , si y sólo si existe una función R de cadenas a cadenas que está computada por una máquina Turing determinista en espacio O (log n) tal que para toda entrada x

x ∈ L si y sólo si R(x) ∈ L′

La función R se llama una reducción de L a L′ .

Completitud

La transitividad de la reducción polinómica nos dice que es una relación de equivalencia, y la relación ≤_L impone un orden parcial en las clases de equivalencia de problemas resultantes, es decir, nos ordena los problemas segun su complejidad. De hecho, la clase P forma la “menor” clase de equivalencia con este orden parcial y, por tanto, puede verse como la clase que contiene los problemas de decisión computacionalmente “más fáciles”. Definiremos ahora que es completo.

Sea C una clase de complejidad, y sea L un lenguaje que pertenece a C, A ∈ C. Diremos que L es C-completo si todo lenguaje L’ ∈ C se puede reducir a L, L' $le; _L.

Otra definición importante es: Un lenguaje es C-dificil si se puede reducir cada lenguaje L’ ∈ C a L, pero no se sabe si es válido que L ∈ C.

Con estos conceptos ya definidos, creo estar lista para en la siguiente entrada hablar de la teoría de complejidad parametrizada, en su momento definiré a fondo otros conceptos que tal vez he pasado por alto, pero serán más fáciles de digerir, si tenemos entendidos estos conceptos, ya sea que dedique una entrada completa o solo haga comentarios en entradas ya publicadas.

---