Clomplejidad Parametrizada

A manera de introducción, dos ejemplos.

En esta entrada, hago una breve introducción a los problemas parametrizados y la noción de la tratabilidad de parámetro fijo (fixed-parameter tractability).

Trabajaremos inicialmente con dos ejemplos, tenemos que tener en cuenta para ambos ejemplos el tamaño de la entrada n y un parametro k, al momento de hacer un análisis de comlejidad parametrizada.

Ejemplo 1: Evaluación de una consulta conjuntiva sobre una base de datos relacional, este tipo de consulta es la que más se presenta en la práctica, en términos de la teoría de complejidad clásica este problema es NP-completo, es decir, intratable.

Ejemplo 2: Verificación Automatizada: el problema aquí es que un sistema de estados finito (estructura Kripke), por ejemplo un circuito, cumpla con cierta propiedad, la propiedad es una formula φ en lógica temporal (LTL), y el problema es decidir si una estructura satisface la formula φ. Este problema es conocido como problema de verificacion del modelo LTL. Visto desde el punto de vista de complejidad clasica, este problema es intratable, es PSPACE-completo.

Estos dos problemas se prestan para hacer un análisis de su complejidad parametrizada. Lo mencione en la primera entrada, pero es bueno recordarlo una vez más, en la teoría de complejidad parametrizada, la complejidad de un problema no solo se mide por el tamaño de la entrada, si no también por un parámetro que se asume es pequeño. De esta manera la complejidad parametrizada tiene como objetivo clasificar problemas NP-duros dentro de otras "escalas" de manera que mucho problemas "duros" que requieren tiempo exponencial cuando su complejidad es medida en terminos del tamaño de la entrada, pero son computables con un parametro k pequeño como describiremos a continuación.

Los problemas arriba mencionados tienen consisten en dos partes cada uno y esas partes tienen tamaño diferente. En la práctica la base de datos y el espacio de estados son muy grandes, mientras que tanto la consulta como la formula tienden a ser pequeños. Como parámetros se eligen el tamaño de la consulta y el tamaño de la formula. Recordemos que tenemos a n es el tamaño de la entrada y k el parámetro. Ahora lo pondremos así:

Ejemplo 1:
n = tamaño de base de datos.
k = tamaño de la consulta.
Este problema se resuelve en O(n^k).

Ejemplo 2:
n = tamaño del espacio de estados.
k = tamaño de la formula.
Este problema se resuelve en O(k 2^2k n).

Si observamos estos dos problemas tienen tiempo de ejecución exponenciales y ambos son polinomiales, para un k fijo (recordar que k es pequeño en comparación de n). Si k = 5, para O(n^k) puede ser un valor extremadamente alto llevaria a un tiempo de computo excesivo, mientras que para el factor 2^2k en O(k 2^2k n) puede llegar a ser desagradable pero aceptable para el problema que sabemos que es PSPACE-completo. Se dice que el problema de verificar el modelo LTL es fixed-parameter tractable (tratable con parametro fijo). La pregunta a resolver sería si el problema de evaluar una consulta conjuntiva es fixed-parameter tractable, es decir, si existe un problema similar al algoritmo del problema de verificar el modelo LTL.




En este caso es necesario observar que las bases de datos suelen ser muy grandes mientras en la practica las consultas tienden a ser pequeña. La evaluación de una consulta de una base de datos puede resolverse en O(n^k, si bien este tiempo es exponencial, notese que el parametro es polinomial para una valor k fijo.

Problemas parametrizados

Hay que recordar que los problemas de decisión se describen como lenguajes sobre alfabetos finitos Σ. Para distinguirlos de los problemas parametrizados, nos referiremos como conjuntos Q ⊆ Σ^* sobre cadenas de Σ

Sea Σ un alfabeto finito:
1) Una parametrizacion de Σ^* es un mapeo κ: Σ^* → N, que es computable en tiempo polinomial.
2) Un problema parametrizado es un par (Q,κ) cque consiste en un conjunto Q ⊆ Σ^* sobre cadenas de Σ y una parametrizacion κ de Σ^*.

Siempre se representara un problema parametrizado de la siguiente forma:

Instancia: x ∈ Σ^*.
Parametro: κ(x)
Problema: Decidir si X ∈ Q.

Ejemplo: Sea SAT el conjunto de todas las formula proposicionales satisfactibles, donde las formulas son codificafas como cadenas sobre un lenguaje finito Σ y sea κ: Σ^* → N una parametrización definida como: κ(x) es igual al numero de variables de x, si x es una formula proposicional o es igual a 1 en otro caso, entonces el problema SAT parametrizado (p - SAT) se puede representar de la siguiente forma:

p-SAT
Instancia:Una formuala proposicional α
Parametro: κ(x)
Problema: Decidir si α es satisfactible.

Tratabilidad con parametro fijo

Sea Σ un alfabeto finito y κ: Σ^* → N una parametrización
1) Un algoritmo con alfabeto de entrada Σ es un algoritmo-ftp con respecto a κ si existe una funcion computable ƒ: N → N y un polinomio p ∈ N₀[X] tal que para cada x ∈ Σ^* el tiempo de ejecución es a lo más:

ƒ(κ(x) p(|x|)

2) Un problema parametrizado (Q, κ) es tratable con parametro fijo, si existe un algoritmo-ftp con respecto a κ que decida Q.

FTP denota a la clase de todo los problemas tratables con parametro fijo.


Por ejemplo: el problema p-SAT es tratable con parametro fijo, el algoritmo de busqueda por fuerza bruta decide una formula φ de tamaño m con k variables en tiempo O(2^k m).

Si Q ∈ PTIME, entonces (Q, κ) ∈ FTP para cada parametrización κ Se tiene entonces que la tratabilidad con parametro fijo relaja la noción clásica de tratabilidad, la decibilidad en tiempo polinomial, un claro ejemplo es el problema de vericacion de modelo LTL.

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.

---

Clases de Complejidad, parte II

Por mucho mucho tiempo se han resuelto tareas de cómputo de muchas maneras y mediante muchos dispositivos desde un abaco hasta la moderna computadora, la pregunta es: ¿Que modelo matemático captura todas las maneras de hacer cómputo? La respuesta es: La máquina de Turing ¹ la cual es un modelo simple pero suficiente para estudiar muchos aspectos de la computación como su eficiencia.

La máquina de Turing es una simple estructura de datos, una cadena de símbolos (cinta); las operaciones permitidas (efectuadas por un "cabezal") son: leer un símbolo de la cadena, moverse hacia la izquierda o derecha y escribir un nuevo símbolo en la posición actual o "expandirse" como explicaremos más adelante, las operaciones a realizar se basan en un conjunto de "reglas". Este modelo es simple pero es capaz de expresar cualquier algoritmo.

Formalmente una máquina de Turing es una tupla M = (Q, Σ,δ, q₀) donde:
Q: es un conjunto finito de estados.
Σ: es un conjunto finito de simbolos, simpre contiene el simbolo en blanco ⌊⌋ y el símbolo de "comienzo" ►.
δ: es una función de transición que mapea Q × Σ → ( Q ∪ {h, "si", "no"}) × Σ × {← (izquierda) ,→ (derecha), - (no moverse)}.
q₀: es el estado inicial q₀ ∈ Q.

Se asume que el estado h es estado de paro (halt), "si" es el estado de aceptación y "no" el estado de rechazo. En pocas palabras δ es una regla que especifica para cada combinación de un estado actual q ∈ Q y un simbolo actual σ ∈ Σ una transición a un estado p, un símbolo ρ se sobreescribe en σ y el cursor se mueve hacia una dirección o se queda en la posición actual, esto es δ(q, σ) → (p, ρ D), donde D = {←, →, - } son las direcciones a las cuales se puede mover el cursor (cabezal que lee los símbolos).

El cabezal siempre realiza una acción hasta que se alcanza algun estado de paro como {h, "si", "no"}) Si es asi se dice que la maquina ha parado (halted). Si el estado "si" se alcanza se dice que la máquina acepta la entrada (la cadena de simbolos), si se alcanza el estado "no" se dice que la máquina rechaza la entrada. Si h se ha alcanzado la salida es la cadena de M al tiempo de paro, la cadena de salida en este caso se denota como y.

Si M acepta o rechaza la entrada x entonces M(x) = "si" o "no" respectivamente. Si se alcanza h, M(x) = y, Si M nunca llega a un estado de paro con la cadena x se escribe M(x) = "↗". En la siguiente figura se muestra en la parte izquiera una máquina de Turing y en la parte derecha se muestra la computación, M simplemente inserta un espacio en blanco entre el símbolo de inicio y la cadena de entrada. Cada operación de la maquina de Turing se define como configuración.



Cuando se va de una configuración a otra se dice que se ha dado un paso en el ejemplo de la figura anterior de la configuración inicial a la final se dieron 15 pasos. Hasta este punto se ha descrito a grandes rasgos que es una máquina de Turing, como "funciona" y unos conceptos básicos, ahora profundizaremos en ciertos conceptos que son muy necesarios para la definición de clases de complejidad.

Máquinas de Turing como algoritmos

Las máquinas de Turing son ideales para resolver cierto tipos de problemas especializados sobre cadenas, como aceptar o decidir "lenguajes". A continuación se listarán una definiciones de utilidad:

Sea L ⊂ (Σ - {⌊⌋})* un lenguaje, es decir, un conjunto de cadenas de simbolos. Sea M una máquina de Turing tal que para cada cadena x ∈ (Σ - {⌊⌋})*. Decimos que M decide L si y solo si x ∈ L, entonces M(x) = "si" y si x ∉ L then M(x) = "no". Si M decide L entonces L es llamado un lenguaje recursivo.

Una máquina Turing acepta un lenguaje L si para toda sucesión x ∈ (Σ - {⌊⌋})* aplica que si x ∈ L, M(x) = “si", pero si x ∉ L, M(x) ="↗". Los lenguajes aceptados por alguna máquina Turing son recursivamente numerables. Nota que si L es recursivo, también es recursivamente numerable.

Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y consisten en las funciones que pueden ser calculadas por una máquina de Turing. Suponga que ƒ es una función de x ∈ (Σ - {⌊⌋})* a Σ* y sea M una maquina de Turing con alfabeto Σ Desimo que M computa a ƒ si para cualqueir cadena x ∈ (Σ - {⌊⌋})*, M(x) = ƒ(x). Si tal M existe, ƒ es llamada una función recursiva.

Maquinas de Turing con multiples cadenas.

Para definir formalmente el tiempo y el espacio requerido por una máquina de Turing para hacer computaciones, se debe introducir una generalización de esta, la máquina de Turing con multiples cadenas o más bien máquina de Turing con k cadenas, donde k >= 1. La máquina se define como anteriormente se hizo, la función de transición decide el siguiente estado igual que antes, solo que ahora decide para cada cadena el símbolo a escribir y la dirección del cabezal viendo el estado y símbolo actual de cada cadena. La salida de la computación de una máquina de Turing de k-cadenas con entrada x es como en la descirta anteriormente (k=1) con la sola diferencia que la salida se lee del última cadena cuando la máquina se detiene. La configuración y el número de pasos se define análogamente a como se definio anteriormente.

Ahora viene lo más importante, si para una maquina con k cintas se llega de una configuración incial a una configuración de paro en t pasos, entonces el tiempo requerido por M sobre la entrada x es t. Es decir, el tiempo requerido es simplemente el número de pasos para parar. Si M(x) ="↗" entonces el tiempo requerido por M sobre x es infinito.

Sea ƒ una función de N a N. Decimos que la maquina M opera con tiempo ƒ(n) para cualquier entrada x, el tiempo requerido por M sobre x es a lo más ƒ(|x|). Supongamos que un lenguaje L ⊂ (Σ - {⌊⌋}) es decidido por una máquina de Turing multicadena en tiempo ƒ(n). Se dice que L ∈ TIME(ƒ(n)). Esto es TIME(ƒ(n)) es un conjunto de lenguajes que pueden ser decididos por máquina de Turing multicadenas que operan con un tiempo acotado por ƒ(n). TIME(ƒ(n)) es una clase de complejidad de tiempo, pero tambien tenemos clases de complejidad de espacio.

Cuando la máquina de Turing para, el cabezal se detiene en cierta posición de la última cinta, denotemos w como la parte izquierda de la cadena tomando en cuenta el simbolo sobre el cual esta el cabezal y u la parte de la cadena a la derecha del cabezal. Entonces el espacio requerido por M es Σ_i=1^k-1|w_iu_i|. Supongase ahora que ƒ es una funcion de N a N. Entonces decimos que una máquina de Turing M opera en un espacio acotado por ƒ(n). Sea L un lenguaje, decimos que L estan en la clase de complejidad de espacio SPACE(ƒ(n)) si existe una máquina de Turing con entrada y salida que decida L y opere en un espacio acotado por ƒ(n).

Maquinas no deterministas

Una máquina no determinista es una tupla M = (Q, Σ,Δ, q₀) donde Q, &Sigma y σ se definen de igual manera que lo hicimos anteriormente, salta a la vista la diferencia, en una máquina no determinista no tiene una sola acción siguiente definida, si no una opción de acciones, Δ no es una función es una relación &Delta ⊂ (Q × Σ) × [( Q × ∪ {h, "si", "no"}) × Σ × {←, →, -}. Esto es para cada combinacion de estado símbolo hay más de una acción a realizar o ninguna.

Una entrada es aceptada si hay mas de una secuencia de opciones no determinadas que resulten en "si". Otras opciones podrían resultar en rechazo, solo una computación aceptable es suficiente. La cadena es rechazada sí y sólo sí no hay secuencias de opciones puede conducir a aceptar la cadena.

Decimos que una máquina N decide un lenguaje L en tiempo ƒ(n), si N decide L y hay k cantidad de pasos de una configuración incial a una configuracion de paro, entonces k <= ƒ(|x|). Esto es, se requiere que N, ademas de aceptar a L, no tengas rutas de computación mas grandes que ƒ(n). El conjunto de lenguajes decididos por una máquina de Turing no determinista en tiempo ƒ es la clase de complejidad NTIME(ƒ(n)).

---

[1] Turing, A.M. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2, 42, 230-265. 1936.