Uma introdução à complexidade parametrizada

• Processo: 21/07076-9
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de novembro de 2021
• Data de Término da vigência: 31 de outubro de 2022
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Carla Negri Lintzmayer
• Beneficiário: Gustavo da Silva Teixeira
• Instituição Sede: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brasil
• Assunto(s): Algoritmos Complexidade Problema computacional
• Palavra(s)-Chave do Pesquisador: Algoritmos | Complexidade Computacional | Complexidade parametrizada | Algoritmos

Resumo

Quando tratamos de problemas computacionais, buscamos sempre desenvolver algoritmos eficientes que os resolvam, para todas as instâncias possíveis. O conceito de eficiência de um algoritmo normalmente refere-se à sua complexidade de tempo ser polinomial no tamanho da entrada. Porém, existem muitos problemas relevantes para os quais não há esperança de que existem algoritmos eficientes que encontrem soluções ótimas para todas as instâncias. Estes problemas constituem as classes denominadas NP-difícil e NP-completo. Tais problemas, por muitas vezes terem aplicações importantes no mundo real, ainda necessitam de alguma solução e, entre as alternativas para lidar com eles, poderíamos pensar em algoritmos que, mesmo não sendo eficientes, devolvessem soluções ótimas com menos consumo de tempo. A teoria da complexidade parametrizada propõe uma alternativa neste sentido, estudando algoritmos que encontram soluções ótimas para todas as instâncias destes problemas em tempo exponencial, mas cuja complexidade exponencial não dependa de todo o tamanho da entrada, mas sim de um valor denominado parâmetro, que representa o tamanho de um determinado aspecto da entrada, e normalmente é bem menor que esta última. Problemas que admitem tais algoritmos são chamados de tratáveis por parâmetro fixo (FPT), e formam a classe de problemas que também denominamos FPT. Este projeto de iniciação científica tem por objetivo introduzir o candidato à teoria da complexidade parametrizada, fornecendo uma visão geral da área, com o estudo dos principais problemas envolvidos, das principais técnicas de desenvolvimento de algoritmos para lidar com problemas FPT e de resultados importantes obtidos na área até então.(AU)