Complejidad Descriptiva.

Hace más de 8 días, encontré unas diapositivas que ayudaron a aclarar mi ideas con respecto a la complejidad parametrizada, la idea general la tengo, pero cuando empecé a hacer la entrada del blog donde iba a empezar a hablar al respecto, tuve un problema. Para empezar a explicar acerca de este tema, tengo que describir dos problemas de los cuales uno no me quedaba claro, el "model checking", me di cuenta que esos capítulos del Papadimitriou a los cuales solo les había dado un vistazo debía estudiarlos a profundidad.

Encontré, si encontré - descubrí, cosas muy interesantes, ya antes había leido de lógica booleana, lógica de primer orden, de segundo orden; hasta hice todos los ejercicios de un libro de "introducción a la lógica". Pero la manera de ver la complejidad computacional después de leer detenidamente esos capítulos, que a veces ciertas frases parecen juegos de palabras o trabalenguas.

Ver los problemas computacionales desde la perspectiva de la lógica, es importante para la teoria de la complejidad. Por su naturaleza expresiva y versátil, no solo es usada para expresar la verdad matemática, si no también la computación a varios niveles.

Por una parte tenemos la lógica booleana (primer nivel) donde tenemos variables booleanas que pueden tomar dos valores de verdad, "verdadero" y "falso", estas se pueden combinar usando conectores booleandos como el "o lógico" (OR), el "y lógico" (AND), y el "no logico". Podemos tener expresiones booleanas llamadas literales, negaciones, conjunciones y disyunciones. Estos es solo la sintaxis, su estructura. Lo importate es su semántica, es decir, su significado. Hay ciertas expresiones "especiales" como la forma normal conjuntiva - CNF ¹ - (conjunciones de disyunciones) y la forma normal disyuntiva - DNF ²- (disyunciones de conjunciones). Lo importante en este nivel es definir la satisfactibilidad y la validez, dos propiedades muy importantes de las expresiones booleanas.

Un problema computacional que se puede tratar a este nivel es de SATIFACTIBILIDAD (o SAT), dada una expresión booleana en CNF, ¿es satisfactible? , de hecho este problema esta en NP exhaustivamente puede resolverse en O(n²2ⁿ). Un caso especial de SAT es el HORNSAT el cual esta en P.

Las expresiones booleanas puede representarse mediante circuitos (grafos) de aquí se desprende problemas como el CIRCUIT SAT y CIRCUIT VALUE los cuales están en NP y P respectivamente.

El siguiente nivel es la lógica de primer orden, aquí se introducen términos como constantes, funciones y relaciones que serán el vocabulario, hay implicaciones, equivalencias y cuantificadores (universal y de existencia). La asignación de verdad para la lógica de primer orden nos lleva a definir un modelo. Cuando se tiene una expresión sobre un vocabulario específico y tenemos un modelo apropiado para este vocabulario, se dice que el modelo satisface a la expresión. En mi caso que trabajo con grafos puse mucha atención a como se describen ciertas propiedades de los grafos en lógica de primer orden, como lo es la simetría, la transitividad, una función sobre el grafo por ejemplo que todos los nodos tengan grado uno, y en como se define un modelo. Este tipo de propiedades y funciones pueden verificarse en tiempo polinomial. Cada propiedad puede transformase en un problema computacional como: Dado un grafo G, ¿tiene cierta propiedad?, para este tipo de problemas se llega a la conclusión que están en P. Pero hay ciertos problemas computacionales que involucran grafos que son pueden ser expresado con lógica de primer orden como REACHABILITY. Para validar expresiones hay veces que hay que rebuscar un modelo que lo satisfaga, se dice entonces que la expresión es satisfactible, otras expresiones sin embargo son satisfactible por cualquier modelo, entonces decimos que la expresión es válida.

Hay ciertos teoremas que todavía me faltan por comprender, pero a grandes rasgos es lo mas importante que pude digerir. En el nivel de lógica de segundo orden, nos permite introducir propiedades como variables haciendo más fácil expresar problemas computacionales. Para cualquier expresión existencial en segundo orden que hacen referencia a grafos el problema esta en NP, si las expresión son cláusuas de Horn, el problema esta en P por ejemplo el problema del camino hamiltoniano.

Todo esto me llamo mas la atención cuando llegue a un enlace interesante. Aquí es donde viene lo importante y por lo cual he titulado a esta entrada "Complejidad Descriptiva".

La complejidad descriptiva, estudia que clases de complejidad computacional pueden ser caracterizadas por el "nivel" de lógica con el cuales se pueden expresar los lenguajes en ellas ³. Con los capítulos que leí acerca de esto y el enlace que encontré, me queda más claro como describir el problema que necesito explicar para abordar la complejidad parametrizada (entrada que deje inconclusa y no he publicado pues no me gusta publicar algo que no he entendido bien) y más adelante describir clases de complejidad parametrizada.

---

[1]. Conjuntive normal form
[2]. Disjuntive normal form
[3]. Descriptive Complexity