Produção Nacional
Evasividade de Propriedades de Grafos
2010; Volume: 4; Issue: 2 Linguagem: Português
10.13037/ras.vol4n2.26
ISSN2179-2518
Autores Tópico(s)Topological and Geometric Data Analysis
ResumoUm problema bastante dificil em computacao e determinar limitantes inferiores nao-triviais para a complexidade de problemas computacionais. Um limitante desse tipo implica que qualquer algoritmo que resolve o problema tem no minimo essa complexidade. Nesse texto, discorreu-se sobre complexidade de propriedades de grafos e sobre uma conjectura de 1973 e ainda nao resolvida sobre a complexidade de propriedades monotonas de grafos. Tambem, expos-se uma solucao parcial para essa conjectura, um resultado de Kahn, Saks & Sturtevant, de 1984 [1], que ate o momento e o unico progresso relevante sobre o problema. O resultado de [1] e por meio de resultados de ponto fixo da acao de grupos sobre certos espacos topologicos.
Referência(s)