Reducciones Parametrizadas e Intratabilidad

Antes que nada debo aclarar un punto, la entrada del 24 de Febrero en realidad tendría que venir despues de la que primera que esta en marzo, por ahi hubo un error tecnico de mi parte, por lo cual me referire a la sesion anterior como la de "Complejidad Parametrizada", una vez hecha la aclaracion empezaré:

En la sesion anterior se introdujo lo que es parametrización, problemas parametrizados y la tratabilidad parametrizada y vimos la clase FPT, ahora abordaremos un tema que es muy importante (además de la complejidad descriptiva) debido a que nos ayudara a definir otras clases de complejidad parametrizada, las reducciones tratables de parametro fijo (Fixed parameter tractable reductions)

Reducciones tratables de parametro fijo.
Principalmente en este apartado se introducen definiciones útiles para temas que abordaremos más adelante.

Sea (Q, κ) y (Q', κ') problemas parametrizados sobre un alfabeto Σ y Σ' respectivamente. Una reduccion fpt de (Q, κ) a (Q', κ') es un mapeo R: Σ &rarrow; Σ' tal que:

1) Para toda x ∈ Σ tenemos que (x ∈ Q ⇔ R(x) ∈ Q')
2) R es computable por un algoritmo-fpt (con respecto a κ). Esto es, existe una funcion computable ƒ y un polinomio p(X) tal que R(x) es computable en tiempo ƒ(κ(x)) ⋅ p(|x|).
3) Hay una función computable g: N → N tal que κ'(R(x)) < g(κ(x)).

Se tiene entonces que FPT es cerrada bajo reducciones fpt. Esto es, si un problema parametrizado (Q, κ) es reducible a un problema parametrizado (Q', κ') y (Q', κ') ∈ FTP, entonces (Q, κ) ∈ FPT.

Se escribe que (Q, κ) ≤^fpt (Q', κ'), si existe una reducción-fpt de (Q, κ) a (Q', κ').

Definamos [(Q, κ)]^fpt como la clase de problemas parametrizados reducibles-fpt a (Q, κ), esto es:
[(Q, κ)]^fpt := {(Q', κ') | (Q', κ') ≤^fpt (Q, κ)}

Si C es una clase de problemas parametrizados, se tiene [C]^fpt := ∪_{(Q, κ) ∈ C} [(Q, κ)]^fpt.

Por lo cual si (Q, κ) ≤^fpt (Q', κ') y (Q', κ') ∈ C entonces (Q, κ) ∈ C.

Y se define lo siguiente (como en teoria de complejidad clasica):

a) (Q, κ) es C-difícil bajo reducciones-fpt si todo problema en C es reducible-fpt a (Q, κ).
b) (Q, κ) es C-completo bajo reducciones-fpt si (Q, κ) ∈ C y (Q, κ) es C-difícil.

Clase para-NP

Se dijo que la clase FPT puede ser vista como una analogía de la clase PTIME, la pregunta es ¿existe una clase análoga a NP?. La clase resultante es la para-NP obtenida de reemplazar "algoritmo" por "algoritmo no determinista" de la definicion de FPT esto puede a ser algo no satisfactorio pero ayuda a aclarar algunas ideas. De la forma en que se define para-NP se pueden derivar clases parametrizadas de las clases de complejidad clasica ¹.

Un problema parametrizado (Q, κ) sobre Σ esta en para-NP, si existe una funcion computable ƒ:N→N y un polinomio p ∈ N₀[X], y un algoritmo no determinista tal que dado x ∈ Σ*, decide si x ∈ Q a lo más en ƒ(κ(x))⋅(p|x|) pasos.

Sea (Q, κ un problema parametrizado sobre un alfabeto Σ, entonces lo siguiente es verdadero:
1) (Q, κ esta en para-NP
2) "(Q, κ) esta en NP despues de una pre-computación sobre el parametro". Esto es, existie un alfabeto Π, una funcion computable π: N → Π* y un problema X ⊆ Σ* × Π* tal que X ∈ NP para todas las instancias x de Q tenemos

x ∈ Q ⇔ (x. π(κ(x))) ∈ X.

3) Q es decidible y "(Q, κ) es eventualmente en NP". Esto es, existe una funcion computable h: N → N u un algoritmo no determinista en tiempo polinomial que sobre la entrara x ∈ Σ* dedice si x ∈ Q en caso de |x| ≤ h(κ)).

Si bien esta definición no da una idea clara de la intratabilidad en el mundo parametrizado una vez mas nos reafrima que la parametrizacion es una relajación, lo que percibo hasta este punto es que la parametrización trata de atraer la intratabilidad a la tratabildad, pero la pregunta aqui es que es lo que hace que un problema parametrizado se acerque a la intratabilidad, esto tiene mucho que ver con su estructura y de ahi se deriva la clase W o mas bien la jerarquia W de la cual hablaremos en entradas siguientes, aun no se como tratar este tema, si dar una sola entrada tratando de ser lo mas entendible posible o dedicarle varias.

---

[1] Flum, G and Grohe, J . Describing parameterized complexity classes. STACS 2002.

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