Complexidade parametrizada

Em ciência da computação, complexidade parametrizada é um ramo da teoria da complexidade computacional que foca em classificar 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 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 . 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 . Consequentemente, se é fixado em um valor pequeno e o crescimento da função sobre é 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 (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 é 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 , 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 e um inteiro não-negativo , possui alguma propriedade que depende de ? 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 , 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 , em que é um alfabeto finito. O segundo componente é chamado de parâmetro do problema.Um problema parametrizado é tratável em parâmetro fixo se a questão “?” pode ser decidida em tempo , em que é uma função arbitrária dependendo unicamente de . A classe de complexidade correspondente é FPT. Por exemplo, há um algoritmo que resolve o problema de cobertura de vértices em tempo , em que é o número de vértices e é 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.