Os cientistas da computação dinamarqueses acabam de resolver um enigma de três décadas. O quebra-cabeça foi proposto na década de 1990 e foi esquecido desde então.
A resolução foi verdadeiramente notável e deu um artigo científico publicado em STOC 2020, a edição deste ano do Simpósio de Teoria Computacional.
Teoria dos grafos, um enigma de três décadas
O quebra-cabeça faz parte do galho matemática é chamada de teoria dos grafos. A teoria dos grafos é, em suma, o estudo dos elementos de um conjunto e suas relações mútuas.
O nome ‘gráficos’ (veja, eles não são mandíbulas) vem do nome das estruturas usadas para resolver esses problemas: gráficos. A princípio, os gráficos se parecem muito com aqueles pequenos jogos de conexão de pontos – sem querer ofender os matemáticos.
Embora pareça simples, não é. Este problema específico envolveu a criação de um algoritmo para resolver a planaridade (a forma de um gráfico de interseção) em um gráfico dinâmico (que muda).
No entanto, há um problema: essas linhas não podem ser cruzadas. Em alguns casos, isso não é possível – pelo menos não em um mapa bidimensional. A situação muda quando gráficos tridimensionais são usados porque existem várias arestas possíveis.
Existe um teorema chamado Teorema de Kuratowski, que foi criado especificamente para o desenvolvimento desta tarefa, que parece simples, mas realmente extenuante.
Alguns problemas atingem um nível de complexidade que torna a resolução manual impraticável, e para isso existem vários algoritmos para os quais um computador pode realizar bilhões ou até trilhões de cálculos por segundo.
E é aí que eles trabalharam. Se os gráficos estáticos já podem representar desafios significativos, imagine um gráfico em constante mudança. A dupla conseguiu avançar em algoritmos estagnados desde os anos 1990.
Um exemplo simples de teoria dos grafos
Gráficos, gráficos estáticos, gráficos dinâmicos, algoritmos … são muito técnicos e enfadonhos, não são? Na verdade não. Vamos entender por meio de um exemplo simples e muito familiar.
Esta imagem abaixo representa Três problemas úteis, A ideia principal por trás disso é simples. No entanto, você só precisa conectar os pontos, seguindo algumas regras.
São três chalés, como podem ver. Também há planos para que três empresas ofereçam três serviços distintos: uma de água, outra de gás e a terceira de energia.
Agora você precisa conectar cada caixa a cada um dos serviços. Isso é simples, não é? No entanto, nenhuma linha pode ser cruzada e você só pode usar um plano, ou seja, apenas essas duas dimensões. Tente fazer isso antes de terminar de ler.
Parece difícil? Na verdade, isso é impossível, como você pode ver na imagem acima. Está matematicamente provado que este não é um gráfico plano. A única maneira de resolver isso é com três dimensões.
Este é apenas um exemplo simples, para ilustração, que pode ser facilmente resolvido com três dimensões. Na mesma foto acima, se você considerar que aquela linha azul que cruza com a amarela, acima, está resolvida. Os problemas resolvidos por computador, no entanto, são muito mais complexos.
Com informações de A ciência do aviso,,