Enigma de três décadas perdido acaba de ser decifrado

Dois cientistas da computação dinamarqueses acabaram de resolver um enigma de três décadas perdido. O enigma havia sido proposto nos anos 1990 e, desde então, foi esquecido pelo tempo. 

A resolução foi realmente notável, e rendeu um artigo científico publicado no STOC 2020, a edição deste ano do Symposium on Theory of Computing (Simpósio de Teoria da Computação).

 Teoria dos grafos, o enigma de três décadas

O enigma faz parte um ramo da matemática chamado de teoria dos grafos. A teoria dos grafos é, em resumo, o estudo de elementos de um conjunto e suas mútuas relações.

O nome ‘grafos’ (veja bem, não são garfos), vem do nome das estruturas utilizadas nas resoluções desses problemas: os grafos. Em um primeiro momento, os grafos se parecem bastante com aqueles joguinhos de ligar os pontos – sem querer ofender os matemáticos. 

Apesar de parecer simples, não é. Este problema específico, envolvia a criação de um algoritmo para se conseguir resolver a planaridade (o formato de um grafo que se cruza) em um gráfico dinâmico (que muda).

Entretanto, há um problema: essas linhas não podem se cruzar. Em alguns casos isso não é possível – pelo menos não em um mapa bidimensional. A situação muda quando se utiliza gráficos em três dimensões, já que há mais arestas possíveis.

Existe um teorema chamado de Teorema de Kuratowski, que foi criado especificamente para auxiliar a desenvolver esta tarefa, que parece simples mas é realmente árdua.

Alguns problemas atingem um nível de complexidade o suficiente para que a resolução manual se torne impraticável, e para isso, há diversos algoritmos, para que um computador, que é capaz de realizar bilhões, ou até trilhões de cálculos por segundo.  

E foi nesse ponto que eles trabalharam. Se gráficos estáticos podem já representar desafios consideráveis, imagina um gráfico em constante mudança. A dupla conseguiu progredir em algoritmos parados desde os anos 1990.

Um exemplo simples da teoria dos grafos

Grafos, gráficos estáticos, gráficos dinâmicos, algoritmos… assunto técnico e chato demais, não? Na verdade não. Vamos entender através de um exemplo simples e bastante famoso. 

Esta imagem abaixo representa o Problema dos Três Utilitários. A ideia principal por trás dele é simples. Você precisa apenas ligar os pontos, seguindo algumas regras, entretanto. 

São, como você pode ver, três chalés. Há, também, no plano, três companhias, que oferecem três serviços diferentes: uma oferece água, a segunda oferece gás, e a terceira, energia. 

Agora, você precisa ligar cada um dos chalés até cada um dos serviços. Isso é simples, correto? Entretanto, você não pode fazer nenhuma linha se cruzar, e pode utilizar somente o plano, ou seja, apenas essas duas dimensões. Tente fazê-lo antes de terminar de ler. 

Parece difícil? Na verdade é impossível, como você pode ver na imagem acima. É provado matematicamente que este não é um gráfico plano. A única forma de resolvê-lo é com três dimensões.

Este é apenas um exemplos simples, para ilustrar, que pode ser facilmente resolvido com três dimensões. Naquela mesma foto acima, se você considerar que aquela linha azul cruzando com a amarela está, na verdade, acima, está resolvido. Os problemas resolvidos computacionalmente, entretanto, são bem mais complicados.

Com informações de Science Alert.