Evasividade de Propriedades de Grafos

Abstract

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.