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 {\displaystyle k} . Consequentemente, se k {\displaystyle k} é fixado em um valor pequeno e o crescimento da função sobre k {\displaystyle 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 {\displaystyle k} é fixado são chamados de problemas parametrizados. Um problema parametrizado que permite...