Teoría de Complejidad Parametrizada, una breve introducción.

Si buscamos en Google "Complejidad Computacional" encontraremos que es una rama de la Teoría de la Computación que se encarga de clasificar problemas computacionales de acuerdo a su dificultad. Donde definen problema computacional como una tarea que se resuelve a través de una computadora.

En la teoría de complejidad computacional [1], los "problemas computacionales" que se abordan son problemas llamados problemas de decisión, es decir, problemas que requieren como respuesta "si" o "no". Por ejemplo: ¿Dado un grafo G = (V, E), se puede colorear con k colores? ¹. Lo que realmente es de interés son los algoritmos que pueden decidir - resolver - nuestros problemas, en sí, nos interesa que tan difícil es resolver el problema y para ello de alguna manera se mide la cantidad de recursos (ya sea tiempo de cómputo o espacio en memoria) requeridos para resolver el problema. Por lo regular se mide el tiempo de cómputo o el espacio requerido en función del tamaño de la instancia ² del problema a resolver. En el caso de los grafos el tamaño de la instancia es el número de nodos.

Para poder clasificar un problema dentro de una clase de complejidad. Una clase de complejidad está especificada por algunos parámetros (de los cuales trataremos en próximas sesiones) como son:

1. Un modelo de cómputo, tal como una Máquina de Turing.
   
2. El modo de hacer el cómputo. Determinista o No determinista.
   
3. El recurso que se desea medir (acotar). Tiempo o espacio.
   
4. Y una función que define una cota tomando como parámetro el tamaño de la instancia.
   

Por lo regular nos interesa que la tasa de crecimiento de las funciones que definen la cota en función del tamaño de la instancia sea polinomial , esto nos indica requerimientos de tiempo de cómputo aceptables, en contraste las tasas de crecimiento exponenciales causan preocupación y podríamos llegar a decir que el problema es intratable, es decir, no tener una solución práctica. Tal es el caso de los problemas que pertenecen a la clase NP-completo, es decir, para estos problemas el tiempo requerido para resolver el problema usando cualquier algoritmo conocido se incrementa rápidamente con el tamaño de la instancia, para versiones algo grandes de instancia del problema podría llevarse millones de años conocer la solución usando el poder de cómputo actual, lo que no es nada práctico.

Ahora que hemos dado una pequeña introducción acerca de la teoría de complejidad computacional "clásica", podemos hablar de la teoría de complejidad parametrizada [2], en la cual, es de interés definir una cota en función del tamaño de la instancia y un parámetro del problema.

Se habla entonces de parametrizar el problema, por ejemplo en el problema de coloreo de grafos, nos interesa aparte del tamaño del grafo, el parámetro k. Es bien sabido que el problema de 3-coloreo (colorear un grafo solo con tres colores) es NP-completo, así como mucho problemas más [3], la idea de parametrizar un problema es que si sabemos que el problema es NP-completo o intratable, en algunos casos solo un pequeño rango de parámetros son realmente importantes en la práctica, lo cual los hace "tratables" dentro de esos rangos, lo cual nos da una idea más optimista acerca de la solución del problema.

Para todo aquel que desee más información acerca del tema o seguir mi blog se recomiendan los siguientes libros:
[1] Papadimitriou, Christos (1994). Computational Complexity (1st ed.). Addison Wesley.
[2] Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer.
[3] Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman.

Conforme vaya creciendo este blog pondré enlaces a literatura interesante que he encontrado. En próximas sesiones abordare mas específicamente temas de complejidad computacional "clásica" que harán mas digerible la teoría de complejidad parametrizada. La idea de mi proyecto doctoral es definir la complejidad computacional en términos no sólo del tamaño de la instancia si no de alguna propiedad estructural de la instancia. Espero sus comentarios.

---

¹ Colorear un grafo se refiere a asignar un color a cada nodo con la restricción que dos nodos adyacentes no pueden tener asignado el mismo color.
² Por instancia del problema, se refiere cuando damos valores a los parámetros del problema, por ejemplo para el coloreo de grafo una instancia del problema es: un grafo con |V| = 5 nodos, |E| = 10 aristas, que se desea colorear con k =3 colores.