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.