Complejidad parametrizada

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.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 claseMuchos problemas tienen la siguiente forma: dado un objetoEn 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.Contiene los problemas tratables de parámetro fijo, los cuales pueden ser resueltos en tiempopero la definición admite funciones que crecen aún más rápido.Dada una fórmula de tamaño m con k variables puede ser verificada mediante fuerza bruta en tiempoSe 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 tiempoTambié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).Un problema parametrzado está en la clase W[i], si toda instanciaLa 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.Las clases en la jerarquía W son también encerradas dentro de fpt-reduction.SAT puede ser enunciado de la manera siguiente: Se puede mostrar que el problema Weighted[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(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, 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