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 ${displaystyle 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 ${displaystyle 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:

Por ejemplo, hay un algoritmo que resuelve el problema de cobertura de vértices en tiempo ${displaystyle O(kn+1.274^{k})}$,^[1]​ donde ${displaystyle n}$ es el número de vértices y ${displaystyle 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.

Contiene los problemas tratables de parámetro fijo, los cuales pueden ser resueltos en tiempo ${displaystyle f(k)cdot {|x|}^{O(1)}}$ para alguna función computable f. Por lo general, esta función se considera como única exponencial, como ${displaystyle 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 ${displaystyle f(n,k)}$ tal como ${displaystyle n^{k}}$. La clase de parámetro fijo lineal (FPL por sus siglas en inglés) es la clase de problemas resolubles en tiempo ${displaystyle 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 ${displaystyle O(2^{k}m)}$. Una cobertura de vértices de tamaño k en un grafo de orden n puede ser encontrada en tiempo ${displaystyle 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 ${displaystyle 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 ${displaystyle 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).

Es una colección de clases de complejidad computacional. Un problema parametrzado está en la clase W[i], si toda instancia ${displaystyle (x,k)}$ puede ser transformada (en tiempo fpt) a un camino combinatorio que tenga un weft de a lo sumo i, tal que ${displaystyle (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] ${displaystyle subseteq }$ W[j] para todo ${displaystyle ileq 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].

Ejemplos de problemas W[1]-completo pueden ser

Ejemplos de problemas W[2]-completos pueden ser

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

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

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

Es la case de problemas que pueden ser decididos en tiempo polinomial mediante un autómata no deterministas en a lo sumo ${displaystyle O(f(k)cdot log n)}$ para computar ${displaystyle (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 ${displaystyle 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 es la clase de problemas parametrizados que pueden ser resueltos en tiempo ${displaystyle n^{f(k)}}$ para alguna función ${displaystyle f}$ computable.

---