Mostrar código-fonte de Complexidade parametrizada

Em [[ciência da computação]], '''complexidade parametrizada''' é um ramo da [[complexidade computacional|teoria da complexidade computacional]] que foca em classificar[[problema computacional|problemas 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 (matemática)|função]] nesses parâmetros. Isso permite a classificação de problemas [[NP-difícil|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 {{harvtxt|Downey|Fellows|1999}}.

Sob a hipótese de que [[P versus NP|P&nbsp;≠&nbsp;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 <math>k</math>. Consequentemente, se <math>k</math> é fixado em um valor pequeno e o crescimento da função sobre <math>k</math> é 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-completo]]s, ou mesmo [[NP-difícil|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 [[Tempo exponencial|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 <math>k</math> é 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 <math>FPT</math>, 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 <math>x</math> e um inteiro não-negativo <math>k</math>, <math>x</math> possui alguma propriedade que depende de <math>k</math>? Por exemplo, para o [[Cobertura de vértices (teoria dos grafos)|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 <math>k</math>, 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 <math>L \subseteq \Sigma^* \times \N</math>, em que <math>\Sigma</math> é um alfabeto finito. O segundo componente é chamado de ''parâmetro'' do problema.

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

Por exemplo, há um algoritmo que resolve o problema de cobertura de vértices em tempo <math>O(kn + 1.274^k)</math>,<ref>{{harvnb|Chen|Kanj|Xia|2006}}</ref> em que <math>n</math> é o número de vértices e <math>k</math> é 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 <math>f(k) \cdot {|x|}^{O(1)}</math> para alguma função computável <math>f</math>. Tipicamente, essa função é vista como unicamente exponencial, como por exemplo <math>2^{O(k)}</math> 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 <math>f(n,k)</math>, como <math>n^k</math>.  A classe '''FPL''' (linear em parâmetro fixo) é a classe de problemas solúveis em tempo <math>f(k) \cdot |x|</math> para alguma função computável <math>f</math> {{harvtxt|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 <math>m</math> com <math>k</math> pode ser verificada com força bruta em tempo <math>O(2^km)</math>. Uma [[cobertura de vértice]] de tamanho <math>k</math> em um grafo de ordem <math>n</math> pode ser encontrada em tempo <math>O(2^kn)</math>, 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 <math>k</math>-coloração em tempo <math>f(k)n^{O(1)}</math> para <math>k=3</math> 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 versus NP|P&nbsp;=&nbsp;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 <math>f(k) + |x|^{O(1)}</math>. 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 (complexidade)|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  [[Algoritmo de aproximação|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 <math>(x, k)</math> pode ser transformada (em tempo fpt) em um circuito combinatório com cardinalidade no máximo ''i'', de modo que <math>(x, k)\in L</math> [[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&nbsp;=&nbsp;''W''[0] and W[''i''] <math>\subseteq</math> ''W''[''j''] para todo <math>i\le j</math>.  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 (teoria dos grafos)|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''] ====
<math>W[t]</math> pode ser definida usando a família de problemas SAT Ponderados Cardinalidade-<math>t</math>-Profundidade-<math>d</math> para <math>d\geq t</math>:
<math>W[t,d]</math> é a classe de problemas parametrizados fpt-redutíveis a esse problema, e <math>W[t] = \bigcup_{d\geq t} W[t,d]</math>.

Nesse caso, '''SAT Ponderados Cardinalidade-<math>t</math>-Profundidade-<math>d</math>''' é o seguinte problema:

* Entrada: Uma fórmula Booleana de profundidade no máximo <math>d</math> e cardinalidade no máximo <math>t</math>, e um número <math>k</math>. 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 <math>k</math>?

Pode ser provado que o problema SAT <math>t</math>-Normalizado Ponderado é completo para <math>W[t]</math> sob reduções fpt.<ref>{{citar periódico|autor =Buss, Jonathan F, Islam, Tarique |título=Simplifying the weft hierarchy |periódico=Theoretical Computer Science |ano=2006 |volume=351 |número=3 |páginas=303–313 |publicado=Elsevier |acessodata=16 de abril de 2014 |doi=10.1016/j.tcs.2005.10.002}}</ref>
Aqui, '''SAT <math>t</math>-Normalizado Ponderado''' é o seguinte problema:

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

==== ''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 <math>O(f(k)\cdot \log n)</math> escolhas não-determinísticas na computação em <math>(x,k)</math> (uma Máquina de Turing ''k''-restrita). {{harvtxt|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 <math>\exp(o(n))m^{O(1)}</math>, 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&nbsp;''P''.

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

{{Expand section|date=April 2011}}

== Notas ==
<references />

== Referências ==
* {{citar periódico
|primeiro1 = Jianer
|último1 = Chen
|primeiro2 = Iyad A.
|último2 = Kanj
|primeiro3 = Ge
|último3 = Xia
|título= Improved Parameterized Upper Bounds for Vertex Cover
|periódico= Mfcs 2006
|páginas= 238–249
|ano= 2006
|doi     = 10.1007/11821069_21
|ref     = harv
|volume  = 4162
}}
* {{citar livro
|último = Downey
|primeiro = Rod G.
|autorlink = Rod Downey
|último2 = Fellows
|primeiro2 = Michael R.
|authorlink2 = Michael Fellows
|título= Parameterized Complexity
|publicado= Springer
|ano= 1999
|url         = http://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html?referer=www.springer.de%2Fcgi-bin%2Fsearch_book.pl%3Fisbn%3D0-387-94883-X
|isbn        = 0-387-94883-X
|ref         = harv
}}
* {{citar livro
|último = Flum
|primeiro = Jörg
|autorlink = Jörg Flum
|último2 = Grohe
|primeiro2 = Martin
|authorlink2 = Martin Grohe
|título= Parameterized Complexity Theory
|ano= 2006
|publicado= Springer
|url         = http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0
|isbn        = 978-3-540-29952-3
|ref         = harv
}}
* {{citar livro
|primeiro = Rolf
|último = Niedermeier
|autorlink = Rolf Niedermeier
|título= Invitation to Fixed-Parameter Algorithms
|publicado= Oxford University Press
|ano= 2006
|url        = http://www.oup.com/uk/catalogue/?ci=9780198566076
|isbn       = 0-19-856607-7
|ref        = harv
}}
* {{citar livro
|primeiro = Martin
|último = Grohe
|autorlink = Martin Grohe
|capítulo= Descriptive and Parameterized Complexity
|título= Computer Science Logic
|publicado= Springer Berlin Heidelberg
|series     = Lecture Notes in Computer Science
|volume     = 1683
|ano= 1999
|páginas= 14-31
|url        = http://dx.doi.org/10.1007/3-540-48168-0_3
|isbn       = 978-3-540-66536-6
|ref        = harv
}}
* The Computer Journal. Volume 51, Numbers 1 and 3 (2008). [http://comjnl.oxfordjournals.org/ 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 ==
* [http://fpt.wikidot.com/ Wiki on parameterized complexity]
* [http://www.sprg.uniroma2.it/home/cesati/research/compendium/ Compendium of Parameterized Problems]

[[Categoria:Teoria da complexidade computacional]]