TRATANDO A INTRATABILIDADE ATRAVÉS DE COMPLEXIDADE PARAMETRIZADA

Abstract

A teoria mais geral de complexidade computacional leva em conta o tamanho da instância de um problema para o cálculo de estimativas do seu tempo de resolução e deixa de fora considerações específicas sobre seus demais parâmetros. Esta abordagem inicial levou a conquistas fundamentais na teoria da computação, porém, na prática, no entanto, outros aspectos devem ser considerados em muitos problemas reais, que podem ser expressos por diferentes valores, além do seu tamanho. Estudamos uma abordagem mais aprofundada da teoria da complexidade computacional, que tenta entender a contribuição de vários parâmetros para o tempo de execução de algoritmos para a realização de tarefas computacionais. Esta abordagem é fruto de uma teoria emergente dos últimos trinta anos, chamada de Complexidade Parametrizada. A partir dela, foram desenvolvidas metodologias para buscar algoritmos mais viáveis para versões restritas e possivelmente relevantes de problemas NP-completos. Diferentemente da análise de pior caso tradicionalmente empregada, esta é uma análise de complexidade mais granularizada que se alinha mais com questões computacionais que surgem na prática. Essa teoria tem se mostrado bastante promissora e possui uma vasta coleção de técnicas algorítmicas, tanto voltadas para a aplicações práticas quanto para o desenvolvimento teórico. Neste trabalho, vamos apresentar definições básicas da teoria da complexidade parametrizada e alguns exemplos de sua aplicação.