Complexidade parametrizada

Em ciência da computação, complexidade parametrizada é um ramo da teoria da complexidade computacional que foca em classificarproblemas computacionais de acordo com sua dificuldade inerente com respeito a múltiplos parâmetros da entrada. A complexidade de um problema é, então, definida como uma função nesses parâmetros. Isso permite a classificação de problemas NP-difíceis em uma escala mais rigorosa que da forma clássica, em que a complexidade do problema é medida de acordo com o número de bits da entrada. O primeiro trabalho sistemático em complexidade parametrizada foi realizado por Downey & Fellows (1999).

Sob a hipótese de que P ≠ NP, existem vários problemas naturais que requerem tempo de execução superpolinomial quando a complexidade é medida apenas em termos do tamanho da entrada, mas são computáveis em tempo polinomial no tamanho da entrada e em tempo exponencial ou pior em um parâmetro $k$. Consequentemente, se $k$ é fixado em um valor pequeno e o crescimento da função sobre $k$ é relativamente pequeno então tais problemas podem ainda ser considerados tratáveis, apesar de sua classificação tradicional como intratável.

A existência de algoritmos eficientes, exatos e determinísticos que resolvam problemas NP-completos, ou mesmo NP-difíceis é considerada improvável, se parâmetros de entrada não são fixados; todos os algoritmos conhecidos que resolvem esses problemas requerem tempo exponencial (ou pelo menos superpolinomial) no tamanho total da entrada. Entretanto, alguns problemas podem ser resolvidos por algoritmos que são exponenciais apenas no tamanho de um parâmetro fixo enquanto são polinomiais no tamanho da entrada. Tal algoritmo é chamado de tratável em parâmetro fixo (fpt-)algoritmo (na sigla em inglês), porque o problema pode ser resolvido eficientemente para valores pequenos do parâmetro fixo.

Problemas em que algum parâmetro $k$ é fixado são chamados de problemas parametrizados. Um problema parametrizado que permite um fpt-algoritmo é dito ser tratável em parâmetro fixo e pertence à classe $FPT$, e o antigo nome para a teoria da complexidade parametrizada era tratabilidade em parâmetro fixo.

Muitos problemas possuem o seguinte formato: dado um objeto $x$ e um inteiro não-negativo $k$, $x$ possui alguma propriedade que depende de $k$? Por exemplo, para o problema da cobertura de vértices, o parâmetro pode ser o número de vértices na cobertura. Em muitas aplicações, por exemplo durante a modelagem de correção de erros, pode-se assumir que o parâmetro é "pequeno" em relação ao tamanho total da entrada. Sendo assim, é interessante verificar se pode-se encontrar um algoritmo que é exponencial apenas em $k$, e não no tamanho da entrada.

Dessa forma, complexidade parametrizada pode ser vista como uma teoria da complexidade bidimensional. Esse conceito é formalizado da seguinte forma:

Um problema parametrizado é uma linguagem $L\subseteq \Sigma ^{*}\times \mathbb {N}$, em que $\Sigma$ é um alfabeto finito. O segundo componente é chamado de parâmetro do problema.

Um problema parametrizado $L$ é tratável em parâmetro fixo se a questão “$(x,k)\in L$?” pode ser decidida em tempo $f(k)\cdot |x|^{O(1)}$, em que $f$ é uma função arbitrária dependendo unicamente de $k$. A classe de complexidade correspondente é FPT.

Por exemplo, há um algoritmo que resolve o problema de cobertura de vértices em tempo $O(kn+1.274^{k})$, em que $n$ é o número de vértices e $k$ é o tamanho da cobertura de vértices. Isso significa que o problema de cobertura de vértices é tratável em parâmetro fixo com o tamanho da solução agindo como parâmetro.

Classes de complexidade

FPT

FPT contém os problemas tratáveis em parâmetro fixo, que são aqueles que podem ser resolvidos em tempo $f(k)\cdot {|x|}^{O(1)}$ para alguma função computável $f$. Tipicamente, essa função é vista como unicamente exponencial, como por exemplo $2^{O(k)}$ mas a definição permite funções que crescem ainda mais rápido. Isso é essencial para grande parte da história inicial da classe. A parte crucial da definição é excluir funções do formato $f(n,k)$, como $n^{k}$. A classe FPL (linear em parâmetro fixo) é a classe de problemas solúveis em tempo $f(k)\cdot |x|$ para alguma função computável $f$ Grohe (1999). FPL é, portanto, uma subclasse de FPT.

Um exemplo é o problema de satisfatibilidade, parametrizado pelo número de variáveis. Uma dada fórmula de tamanho $m$ com $k$ pode ser verificada com força bruta em tempo $O(2^{k}m)$. Uma cobertura de vértice de tamanho $k$ em um grafo de ordem $n$ pode ser encontrada em tempo $O(2^{k}n)$, então esse problema está, também, em FPT.

Um problema que se pensa não estar em FPT é o problema de Coloração de grafos parametrizado pelo número de cores. É sabido que 3-coloração é NP-difícil, e um algoritmo para um grafo $k$-coloração em tempo $f(k)n^{O(1)}$ para $k=3$ rodaria em tempo polinomial para o tamanho da entrada. Portanto, se o problema de coloração de grafos parametrizado para o número de cores estiver em FPT, então P = NP.

Há uma série de definições alternativas para FPT. Por exemplo, o requerimento de tempo de execução pode ser substituído por $f(k)+|x|^{O(1)}$. Inclusive, um problema parametrizado está em FPT se possui um "kernel". Kernelização é uma técnica de pré-processamento que reduz a instância original ao seu "kernel absoluto", uma instância possivelmente bem menor que é equivalente à instância original mas possui um tamanho que é limitado à função no parâmetro.

FPT é fechada sob uma redução chamada redução fpt, que simultaneamente preserva o tamanho da instância e o parâmetro.

Obviamente, FPT contém todos os problemas computáveis de tempo polinomial. Ademais, contém todos os problemas de otimização em NP que permitem um esquema de aproximação em tempo polinomial.

Hierarquia W

A hierarquia W é uma coleção de classes de complexidade computacional. Um problema de parametrização está na classe W[i], se toda instância $(x,k)$ pode ser transformada (em tempo fpt) em um circuito combinatório com cardinalidade no máximo i, de modo que $(x,k)\in L$ se e somente se há uma valoração satisfatível para as entradas, que valora 1 para no máximo k entradas. A altura é, portanto, o maior número de unidades lógicas com número de entradas ilimitado em qualquer caminho da entrada para a saída. O número de unidades lógicas com número de entradas limitado nos caminhos deve ser limitado por uma constante válida para todas as instâncias do problema.

Note que FPT = W[0] and W[i] $\subseteq$ W[j] para todo $i\leq j$. As classes na hierarquia W são também fechadas sob redução fpt.

Muitos problemas computacionais naturais ocupam os níveis mais baixos, W[1] and W[2].

W[1]

Exemplos de problemas W[1]-completos incluem

• decidir se dado grafo contém um clique de tamanho k
• decidir se dado grafo contém um Conjunto independente de tamanho k
• decidir se uma dada máquina de Turing não-determinística de única fita aceita uma palavra em k passos (problema da "aceitação curta por máquinas de Turing")

W[2]

Exemplos de problemas W[2]-completos incluem

• decidir se um dado grafo possui um conjunto dominante de tamanho k
• decidir se uma dada máquina de Turing multi-fita não-determinística aceita em k passos

W[t]

$W[t]$ pode ser definida usando a família de problemas SAT Ponderados Cardinalidade-$t$-Profundidade-$d$ para $d\geq t$: $W[t,d]$ é a classe de problemas parametrizados fpt-redutíveis a esse problema, e $W[t]=\bigcup _{d\geq t}W[t,d]$.

Nesse caso, SAT Ponderados Cardinalidade-$t$-Profundidade-$d$ é o seguinte problema:

• Entrada: Uma fórmula Booleana de profundidade no máximo $d$ e cardinalidade no máximo $t$, e um número $k$. A profundidade é o número máximo de portões em qualquer caminho da raiz para uma folha, e a cardinalidade é o número máximo de portões com número de entradas no mínimo três em qualquer caminho da raiz para uma folha.
• Questão: A fórmula possui uma valoração satisfatível de peso Hamming no máximo $k$?

Pode ser provado que o problema SAT $t$-Normalizado Ponderado é completo para $W[t]$ sob reduções fpt. Aqui, SAT $t$-Normalizado Ponderado é o seguinte problema:

• Entrada: Uma fórmula Booleana de profundidade no máximo $t$ com um portão AND no topo, e um número $k$.
• Questão: A fórmula possui uma valoração satisfeitora de peso Hamming no máximo $k$?

W[P]

W[P] é a classe de problemas que podem ser decididos por uma máquina de Turing não-determinística de tempo polinomial que faz no máximo $O(f(k)\cdot \log n)$ escolhas não-determinísticas na computação em $(x,k)$ (uma Máquina de Turing k-restrita). Flum & Grohe (2006)

É sabido que FPT está contida em W[P], e acredita-se que a inclusão é própria. Entretanto, resolver esse problema implicaria em uma solução para o problema P versus NP.

Outras conexões com complexidade computacional não-parametrizada são que: FPT é igual a W[P] se e somente se a satisfatibilidade de circuito pode ser decidida em tempo $\exp(o(n))m^{O(1)}$, ou se e somente se existe uma função não-limitada, não-decrescente e computável de modo que todas as linguagens reconhecidas por uma máquina de Turing não-determinística de tempo polinomial usando f(n)log n escolhas não-determinísticas in P.

XP

XP é a classe de problemas parametrizados que podem ser solucionados em tempo $n^{f(k)}$ para alguma função computável $f$.

Referências

• Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006). «Improved Parameterized Upper Bounds for Vertex Cover». Mfcs 2006. 4162: 238–249. doi:10.1007/11821069_21 
• Downey, Rod G.; Fellows, Michael R. (1999). Parameterized Complexity. [S.l.]: Springer. ISBN 0-387-94883-X 
• Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. [S.l.]: Springer. ISBN 978-3-540-29952-3 
• Niedermeier, Rolf (2006). Invitation to Fixed-Parameter Algorithms. [S.l.]: Oxford University Press. ISBN 0-19-856607-7 
• Grohe, Martin (1999). «Descriptive and Parameterized Complexity». Computer Science Logic. Col: Lecture Notes in Computer Science. 1683. [S.l.]: Springer Berlin Heidelberg. pp. 14–31. ISBN 978-3-540-66536-6 
• 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.

Ligações externas

• Wiki on parameterized complexity
• Compendium of Parameterized Problems