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.
