Complejidad parametrizada

En ciencias de la computación, la complejidad parametrizada es una rama de la teoría de la complejidad computacional que se centra en la clasificación de problemas computacionales de acuerdo a su dificultad con respecto a varios parámetros de la entrada. La complejidad de un problema se expresa entonces mediante una función en esos parámetros. Esto permite clasificar los problemas NP-duros en una escala más fina que en la configuración clásica, donde la complejidad de un problema sólo se mide por el número de bits en la entrada. Los primeros aportes sobre complejidad parametrizada fueron realizados por Downey y Fellows (1999).

Bajo el supuesto de que P ≠ NP, existen muchos problemas naturales que requieren un tiempo computacional superpolinomial cuando la complejidad se mide en términos del tamaño de la entrada solamente, pero que son computables en un tiempo polinomial con respecto al tamaño de la entrada y exponencial o peor en un parámetro k. Por lo tanto, si k se fija en un valor pequeño y el crecimiento de k es relativamente pequeño, entonces este tipo de problemas todavía puede considerarse "manejable" a pesar de su clasificación tradicional como "intratable".

La existencia de algoritmos eficientes, exactos y deterministas para solucionar problemas NP-completo, o por otra parte NP-duro, se considera poco probable, si los parámetros de entrada no son fijos; todos los algoritmos conocidos para resolver estos problemas requieren tiempo exponencial (o al menos superpolinomial) en el tamaño total de la entrada. Sin embargo, algunos problemas pueden ser resueltos por algoritmos que son sólo exponencial en el tamaño de un parámetro fijo y a la vez polinomiales en el tamaño de la entrada. Tales algoritmos son llamados fixed-paramater tractable (fpt-algorithm), debido a que el problema puede resolverse eficientemente para valores pequeños del parámetro fijo.

Problemas en los que se fije algún parámetro k se llaman problemas parametrizados. Un problema parametrizado por algún algoritmo FPT se dice que es un problema tratable de parámetro fijo (fixed-parameter tractable) y pertenece a la clase $FPT$, de ahí que el primer nombre que recibiera la teoría de complejidad parametrizada fue tratabilidad de parámetro fijo (fixed-parameter tractability).

Muchos problemas tienen la siguiente forma: dado un objeto $x$ y un entero no negativo k, determinar si x cumple alguna propiedad que depende de k. Por ejemplo, para el problema de cobertura de vértices, el parámetro puede ser el número de vértices en la cobertura. En muchas aplicaciones, por ejemplo, al modelar la corrección de errores, se puede asumir que el parámetro va a ser “pequeño” comparado con el tamaño total de la entrada. Entonces es interesante ver si podemos encontrar un algoritmo que sea exponencial sólo en k, y no en el tamaño de entrada.

De esta manera, la complejidad parametrizada puede verse como un tipo de teoría de la complejidad de dos dimensiones. Este concepto se formaliza de la siguiente forma:

Un problema parametrizado es un lenguaje $L\subseteq \Sigma ^{*}\times \mathbb {N}$, donde $\Sigma$ es un alfabeto finito. El segundo componente sería el parámetro del problema.

Un problema parametrizado $L$ es un fpt si la interrogante “¿$(x,k)\in L$?” puede ser resuelta en tiempo $f(k)\cdot |x|^{O(1)}$, donde $f$ es una función arbitraria que depende sólo de $k$. La clase de complejidad correspondiente se llama FPT.

Por ejemplo, hay un algoritmo que resuelve el problema de cobertura de vértices en tiempo $O(kn+1.274^{k})$,​ donde $n$ es el número de vértices y $k$ es el tamaño de la cobertura. Esto significa que la cobertura de vértice es fpt tomando como parámetro el tamaño de la solución.

Clases de Complejidad

FPT

Contiene los problemas tratables de parámetro fijo, los cuales pueden ser resueltos en tiempo $f(k)\cdot {|x|}^{O(1)}$ para alguna función computable f. Por lo general, esta función se considera como única exponencial, como $2^{O(k)}$ pero la definición admite funciones que crecen aún más rápido. Esto es esencial para una gran parte de la historia temprana de esta clase. La parte esencial de la definición es excluir funciones de la forma $f(n,k)$ tal como $n^{k}$. La clase de parámetro fijo lineal (FPL por sus siglas en inglés) es la clase de problemas resolubles en tiempo $f(k)\cdot |x|$ para alguna función computable f [Grohe, 1999]. FPL es una subclase de FPT.

Un ejemplo es el problema de satisfacibilidad, parametrizado por el número de variables. Dada una fórmula de tamaño m con k variables puede ser verificada mediante fuerza bruta en tiempo $O(2^{k}m)$. Una cobertura de vértices de tamaño k en un grafo de orden n puede ser encontrada en tiempo $O(2^{k}n)$, por tanto este problema está también en FPT.

Un ejemplo de un problema que no pertenece a esta clase es la coloración de un grafo parametrizada por el número de colores. Se conoce que el problema de saber si un grafo se puede colorear con a lo sumo 3 colores es NP-duro y un algoritmo para grafos k-coloreables de tiempo $f(k)n^{O(1)}$ para k=3 corre en tiempo polinomial en el tamaño de la entrada. Por tanto, si este problema es parametrizado en el número de colores dentro de FPT, entonces P=NP.

Hay varias alternativas para definir FPT. Por ejemplo, el requerimiento de tiempo computacional puede ser remplazado por $f(k)+|x|^{O(1)}$. También, un problema parametrizado está en FPT si este tiene un cierto kernel. La Kernelización es un preproceso técnico que reduce la instancia original a este “kernel fuerte”, una posible instancia mucho más pequeña que es equivalente a la instancia original pero tiene un tamaño acotado por una función en el parámetro.

FPT es encerrada dentro de una reducción parametrizada llamada fpt-reduction, la cual simultáneamente preserva el tamaño de la instancia y el parámetro.

Obviamente, FPT contiene a todos los problemas de orden polinomial. Además, contiene a todos los problemas de optimización en NP que tienen un esquema de aproximación polinomial (Fully polynomial-time approximation scheme).

Jerarquía W

Es una colección de clases de complejidad computacional. Un problema parametrzado está en la clase W[i], si toda instancia $(x,k)$ puede ser transformada (en tiempo fpt) a un camino combinatorio que tenga un weft de a lo sumo i, tal que $(x,k)\in L$ si y solo si existe una asignación satisfactoria para la entrada, la cual asigne 1 a lo sumo k entradas. La altura es el mayor número de unidades lógicas en algún camino desde la entrada hasta la salida. El número de unidades lógicas acotadas en el camino debe ser limitado por una constante que encierre a todas las instancias del problema. Notar que FPT = W[0] y W[i] $\subseteq$ W[j] para todo $i\leq j$. Las clases en la jerarquía W son también encerradas dentro de fpt-reduction. Muchos problemas computacionales naturales ocupan los niveles más bajos, W[1] y W[2].

W[1]

Ejemplos de problemas W[1]-completo pueden ser

• Decidir si un grafo dado contiene un clique de tamaño k
• Decidir si un grafo dado contiene un conjunto independiente de tamaño k
• Decidir si un autómata no determinista reconoce la cadena con k pasos (problema de “aceptación mínima de un autómata”).

W[2]

Ejemplos de problemas W[2]-completos pueden ser

• Decidir si un grafo dado contiene un conjunto dominante de tamaño k.
• Decidir una máquina de Turing con cinta multi-pista reconoce la cadena usando k pasos (problema de “aceptación mínima de una máquina de Turing con cinta multi-pista”).

W[t]

Puede ser definido usando la familia de problemas Weighted Weft-$t$-Depth-$d$ SAT con $d\geq t$ : $W[t,d]$ es la clase de problemas parametrizados que se fpt-reduce a este problema, y $W[t]=\bigcup _{d\geq t}W[t,d]$.

El problema Weighted Weft-$t$-Depth-$d$ SAT puede ser enunciado de la manera siguiente:

• Entrada: Una fórmula boleana de profundidad a lo sumo $d$ y "weft" menor que $t$, y un número $k$. La profundidad es el máximo número de nodos en algún camino desde la raíz a una hoja, y el weft es el máximo número de nodos de entradas en algún camino de la raíz a una hoja.
• Pregunta: ¿Existe una asignación satisfactoria para dicha fórmula en la que Hamming weight sea menor que $k$?

Se puede mostrar que el problema Weighted $t$-Normalize SAT es completo para $W[t]$ dentro de fpt-reductions.​ Este problema se puede plantear como:

• Entrada: Una fórmula boleana con profundidad a lo sumo $t$ y un AND en el tope, y un número $k$.
• Pregunta: ¿Existe una asignación satisfactoria para dicha fórmula en la que Hamming weight sea menor que $k$?

W[P]

Es la case de problemas que pueden ser decididos en tiempo polinomial mediante un autómata no deterministas en a lo sumo $O(f(k)\cdot \log n)$ para computar $(x,k)$ (a k-restricted Turing-machine).Flum y Grohe (2006)

Se sabe que FPT está incluido en W[P], y la inclusión es considerada estricta. Sin embargo, resolver este problema debe implicar la solución de la relación P contra NP.

Otras conexiones para la complejidad computacional no parametrizada son que FPT igual W[P] si y solo si el camino de satisfacibilidad puede ser decidido en tiempo $\exp(o(n))m^{O(1)}$, o si y solo si hay una computable, no decreciente, función f tal que todos los lenguajes reconocido en tiempo polinomial mediante un autómata no determinista usando f(n)log(n) están en P.

XP

XP es la clase de problemas parametrizados que pueden ser resueltos en tiempo $n^{f(k)}$ para alguna función $f$ computable.

Referencias

• Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006). «Improved Parameterized Upper Bounds for Vertex Cover». Mfcs 2006 4162: 238-249. doi:10.1007/11821069_21. 
• Downey, Rod G.; Fellows, Michael R. (1999). Parameterized Complexity. Springer. ISBN 0-387-94883-X. 
• Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3. Archivado desde el original el 18 de noviembre de 2007. Consultado el 23 de diciembre de 2014. 
• Niedermeier, Rolf (2006). Invitation to Fixed-Parameter Algorithms. Oxford University Press. ISBN 0-19-856607-7. Archivado desde el original el 24 de septiembre de 2008. 
• The Computer Journal. Volume 51, Numbers 1 and 3 (2008). The Computer Journal. Special Double Issue on Parameterized Complexity with 15 survey articles, book review, and a Foreword by Guest Editors R. Downey, M. Fellows and M. Langston.
• Grohe, Martin (1999). Descriptive and Parameterized Complexity, Appeared in Computer Science Logic, 13th International Workshop (CSL'99), Lecture Notes in Computer Science 1683, pp. 264 – 273, Springer-Verlag 1999.

Enlaces externos

• Wiki on parameterized complexity
• Compendium of Parameterized Problems

• Datos: Q1570441