Complexitat parametrizada

En ciències de la computació, la complexitat parametrizada és una branca de la teoria de la complexitat computacional que se centra en la classificació de problemes computacionals d'acort a la seua dificultat sobre varis paràmetros de l'entrada. La complexitat d'un problema s'expressa llavors per mig d'una funció en eixos paràmetros. Açò permet classificar els problemes NP-durs en una escala més fina que en la configuració clàssica, a on la complexitat d'un problema només es medix pel número de bits en l'entrada. Els primers aportes sobre complexitat parametrizada varen ser realisats per Downey y Fellows (1999).

Baixe el supòsit de que P ≠ NP, existixen molts problemes naturals que requerixen un temps computacional superpolinomial quan la complexitat es medix en térmens del tamany de l'entrada solament, pero que són computables en un temps polinomial sobre el tamany de l'entrada i exponencial o pijor en un paràmetro k. Per lo tant, si k es fixa en un valor chicotet i el creiximent de k és relativament menut, llavors este tipo de problemes encara pot considerar-se "manejable" a pesar de la seua classificació tradicional com "intractable".

L'existència d'algoritmes eficients, exactes i determinista per a solucionar problemes NP-complet, o per una atra part NP-dur, es considera poc provable, si els paràmetros d'entrada no són fixos; tots els algoritmes coneguts per a resoldre estos problemes requerixen temps exponencial (o a lo manco superpolinomial) en el tamany total de l'entrada. No obstant, alguns problemes poden ser resolts per algoritmes que són només exponencial en el tamany d'un paràmetro fix i al mateix temps polinomiales en el tamany de l'entrada. Tals algoritmes són cridats fixed-paramater tractable (fpt-algorithm), degut a que el problema pot resoldre's eficientemente per a valors menuts del paràmetro fix.

Problemes en els que es fixe algun paràmetro k es diuen problemes parametrizados. Un problema parametrizado per algun algoritme FPT es diu que és un problema tractable de paràmetro fix (fixed-parameter tractable) i pertany a la classe $FPT$, d'ahí que el primer nom que rebera la teoria de complexitat parametrizada va ser tratabilidad de paràmetro fix (fixed-parameter tractability).

Molts problemes tenen la següent forma: donat un objecte $x$ i un sancer no negatiu k, determinar si x complix alguna propietat que depén de k. Per eixemple, per al problema de cobertura de vèrtiços, el paràmetro pot ser el número de vèrtiços en la cobertura. En moltes aplicacions, per eixemple, en modelar la correcció d'errors, es pot assumir que el paràmetro va a ser “menut” comparat en el tamany total de l'entrada. Llavors és interessant vore si podem trobar un algoritme que siga exponencial només en k, i no en el tamany d'entrada.

D'esta manera, la complexitat parametrizada pot vore's com un tipo de teoria de la complexitat de dos dimensions. Este concepte es formalisa de la següent forma:

Un problema parametrizado és un llenguage $L\subseteq {\Sigma }^{*}\times \mathbb{N}$, a on $\Sigma$ és un alfabet finito. El segon component seria el paràmetro del problema.

Un problema parametrizado $L$ és un fpt si l'interrogant “¿$(x,k)\in L$?” pot ser resolta en temps $f(k)\cdot |x{|}^{O(1)}$, a on $f$ és una funció arbitrària que depén només de $k$. La classe de complexitat corresponent es diu FPT.

Per eixemple, hi ha un algoritme que resol el problema de cobertura de vèrtiços en temps $O(kn+1.274^k)$, a on $n$ és el número de vèrtiços i $k$ és el tamany de la cobertura. Açò significa que la cobertura de vèrtiç és fpt prenent com a paràmetro el tamany de la solució.

Classes de Complexitat

FPT

Conté els problemes tractables de paràmetro fix, els quals poden ser resolts en temps $f(k)\cdot {|x|}^{O(1)}$ per a alguna funció computable f. Per lo general, esta funció es considera com a única exponencial, com $2^{O(k)}$ pero la definició admet funcions que creixen encara més ràpit. Açò és essencial per a una gran part de l'història primerenca d'esta classe. La part essencial de la definició és excloure funcions de la forma $f(n,k)$ tal com $n^k$. La classe de paràmetro fix llineal (FPL per les seues sigles en anglés) és la classe de problemes resolubles en temps $f(k)\cdot |x|$ per a alguna funció computable f [Grohe, 1999]. FPL és una subclasse de FPT.

Un eixemple és el problema de satisfacibilidad, parametrizado pel número de variables. Donada una fòrmula de tamany m en k variables pot ser verificada per mig de força bruta en temps $O(2^{k}m)$. Una cobertura de vèrtiços de tamany k en un grafo d'orde n pot ser trobada en temps $O(2^{k}n)$, per tant este problema està també en FPT.

Un eixemple d'un problema que no pertany a esta classe és la coloració d'un grafo parametrizada pel número de colors. Es coneix que el problema de saber si un grafo es pot colorear en com a molt 3 colors és NP-dur i un algoritme per a grafos k-coloreables de temps $f(k)n^{O(1)}$ per a k=3 corre en temps polinomial en el tamany de l'entrada. Per tant, si este problema és parametrizado en el número de colors dins de FPT, llavors P=NP.

Hi ha vàries alternatives per a definir FPT. Per eixemple, el requeriment de temps computacional pot ser remplazado per $f(k)+|x{|}^{O(1)}$. També, un problema parametrizado està en FPT si este té un cert kernel. La Kernelización és un preproceso tècnic que reduïx l'instància original a este “kernel fort”, una possible instància molt més chicoteta que és equivalent a l'instància original pero té un tamany acotat per una funció en el paràmetro.

FPT és tancada dins d'una reducció parametrizada cridada fpt-reduction, la qual simultàneament preserva el tamany de l'instància i el paràmetro.

Òbviament, FPT conté a tots els problemes d'orde polinomial. Ademés, conté a tots els problemes d'optimisació en NP que tenen un esquema d'aproximació polinomial (Fully polynomial-clave approximation scheme).

Jerarquia W

És una colecció de classes de complexitat computacional. Un problema parametrzado està en la classe W[i], si tota instància $(x,k)$ pot ser transformada (en temps fpt) a un camí combinatori que tinga un weft de com a molt i, tal que $(x,k)\in L$ si i solament si existix una assignació satisfactòria per a l'entrada, la qual assigne 1 com a molt k entrades. L'altura és el major número d'unitats llògiques en algun camí des de l'entrada fins a l'eixida. El número d'unitats llògiques acotades en el camí deu ser llimitat per una constant que tanque a totes les instàncies del problema. Notar que FPT = W[0] i W[i] $\subseteq$ W[j] para tot $i\le j$. Les classes en la jerarquia W són també tancades dins de fpt-reduction. Molts problemes computacionals naturals ocupen els nivells més baixos, W[1] i W[2].

W[1]

Eixemples de problemes W[1]-complet poden ser

• Decidir si un grafo dau conté un clique de tamany k
• Decidir si un grafo dau conté un conjunt independent de tamany k
• Decidir si un autómata no determinista reconeix la cadena en k passos (problema de “acceptació mínima d'un autómata”).

W[2]

Eixemples de problemes W[2]-complets poden ser

• Decidir si un grafo dau conté un conjunt dominant de tamany k.
• Decidir una màquina de Turing en cinta multi-pista reconeix la cadena usant k passos (problema de “acceptació mínima d'una màquina de Turing en cinta multi-pista”).

W[t]

Pot ser definit usant la família de problemes Weighted Weft-$t$-Depth-$d$ SAT en $d\ge t$ : $W[t,d]$ és la classe de problemes parametrizados que es fpt-reduïx a este problema, i $W[t]=\bigcup _{d\ge t}W[t,d]$.

El problema Weighted Weft-$t$-Depth-$d$ SAT pot ser enunciat de la manera següent:

• Entrada: Una fòrmula boleana de profunditat com a molt $d$ i "weft" menor que $t$, i un número $k$. La profunditat és el màxim número de nodos en algun camí des de la raïl a un full, i el weft és el màxim número de nodos d'entrades en algun camí de la raïl a un full.
• Pregunta: ¿Existix una assignació satisfactòria para dita fòrmula en la que Hamming weight siga menor que $k$?

Es pot mostrar que el problema Weighted $t$-Normalize SAT és complet per a $W[t]$ dins de fpt-reductions. Este problema es pot plantejar com:

• Entrada: Una fòrmula boleana en profunditat com a molt $t$ i un AND en el top, i un número $k$.
• Pregunta: ¿Existix una assignació satisfactòria para dita fòrmula en la que Hamming weight siga menor que $k$?

W[P]

És la case de problemes que poden ser decidits en temps polinomial per mig d'un autómata no determinista en com a molt $O(f(k)\cdot \log n)$ per a computar $(x,k)$ (a k-restricted Turing-machine).Flum y Grohe (2006)

Se sap que FPT està inclós en W[P], i l'inclusió és considerada estricta. No obstant, resoldre este problema deu implicar la solució de la relació P contra NP.

Atres conexions per a la complexitat computacional no parametrizada són que FPT igual W[P] si i solament si el camí de satisfacibilidad pot ser decidit en temps $\exp (o(n))m^{O(1)}$, o si i solament si hi ha una computable, no decreixent, funció f tal que tots els llenguages reconegut en temps polinomial per mig d'un autómata no determinista usant f(n)log(n) estan en P.

XP

XP és la classe de problemes parametrizados que poden ser resolts en temps $n^{f(k)}$ per a alguna funció $f$ computable.

Referències

• Flum, Jörg (2006). Parameterized Complexity Theory, Springer. ISBN 978-3-540-29952-3.
• The Computer Journal. Volume 51, Numbers 1 and 3 (2008). The Computer Journal. Special Double Issue on Parameterized Complexity with 15 survey articles, book review, and a Foreword by Guest Editors R. Downey, M. Fellows and M. Langston.
• Grohe, Martin (1999). Descriptive and Parameterized Complexity, Appeared in Computer Science Logic, 13th International Workshop (CSL'99), Lecture Notes in Computer Science 1683, pp. 264 – 273, Springer-Verlag 1999.