Evasividade de Propriedades de Grafos

Jair Donadelli

Resumo


Um problema bastante difícil em computação é determinar limitantes inferiores não-triviais para a complexidade de problemas computacionais. Um limitante desse tipo implica que qualquer algoritmo que resolve o problema tem no mínimo essa complexidade. Nesse texto, discorreu-se sobre complexidade de propriedades de grafos e sobre uma conjectura de 1973 e ainda não resolvida sobre a complexidade de propriedades monótonas de grafos. Também, expôs-se uma solução parcial para essa conjectura, um resultado de Kahn, Saks & Sturtevant, de 1984 [1], que até o momento é o único progresso relevante sobre o problema. O resultado de [1] é por meio de resultados de ponto fixo da ação de grupos sobre certos espaços topológicos.

Palavras-chave


Complexidade de Algoritmos; Teoria dos Grafos; Métodos Topológicos

Texto completo:

PDF


DOI: http://dx.doi.org/10.13037/ras.vol4n2.26

Apontamentos

  • Não há apontamentos.


Revista de Informática Aplicada - USCS/UFABC