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.