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...