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 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 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 . Bajo el supuesto de que , existen muchos problemas naturales que requieren un 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 , 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 (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 , 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 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 , donde es un alfabeto finito. El segundo componente sería el parámetro del problema.Un problema parametrizado es un fpt si la interrogante “¿?” puede ser resuelta en tiempo , donde es una función arbitraria que depende sólo de . La clase de complejidad correspondiente se llama FPT. Por ejemplo, hay un algoritmo que resuelve el problema de cobertura de vértices en tiempo ,​ donde es el número de vértices y 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.