Evasividade de Propriedades de Grafos

Autores

  • Jair Donadelli UFPR

DOI:

https://doi.org/10.13037/ria.vol4n2.311

Palavras-chave:

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

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.

Downloads

Não há dados estatísticos.

Downloads

Publicado

2010-03-30

Edição

Seção

Artigos Originais