Há alguns cientistas da computação dinamarqueses resolvido um quebra-cabeça matemático que permaneceu adormecido por décadas, depois que os pesquisadores não fizeram nenhum progresso substancial nele desde os anos 1990.

O problema abstrato em questão é parte do que é chamado teoria dos grafose especifica especificamente o desafio de encontrar um algoritmo para resolver a planura de um gráfico dinâmico. Isso pode parecer um pouco desconcertante, então, se sua teoria dos gráficos estiver um pouco enferrujada, há uma maneira muito mais divertida e acessível de pensar sobre as mesmas ideias inerentes.

Remonta a 1913, embora conceitos matemáticos muito mais distantes possam provavelmente ser rastreados, um quebra-cabeça chamado de problema de três serviços foi publicado.

think about que há três casas alinhadas em uma linha, que você pode desenhar em um pedaço de papel. Abaixo deles, você também pode encontrar três serviços diferentes: água, gás e luz.

Solução de três serviços com cruzamento de linha. (CMG Lee / Wikimedia Commons / CC BY-SA 4.0)

O desafio é traçar linhas neste gráfico simples, conectando os três utilitários a cada casa. Mas há um problema: nenhuma das linhas (nove no complete) do papel pode cruzar entre eles. Você consegue pensar em uma maneira de combinar tudo sem nenhuma das conexões sendo intercaladas?

No sentido mais convencional: em uma folha de papel regular e bidimensional, como um exemplo de gráfico plano – não é possível resolver o problema dos três utilitários. Embora inconveniente, nem todas essas casas podem receber suas conexões.

Mas o problema das três utilidades não é um quebra-cabeça a ser resolvido, mas um exemplo de como alguns tipos de redes gráficas não são planas, ou seja, podem ter arestas (linhas) conectando seus vários vértices (casas e utilitários). sem cruzar as linhas.

Quando se trata de gráficos mais complexos envolvendo mais vértices, Teorema de Kuratowski ajuda os matemáticos a determinar se os gráficos são planos ou não e, desde os anos 1970, os pesquisadores também vêm desenvolvendo algoritmos para fazer a mesma coisa com mais rapidez.

Mesmo assim, depois de um closing avanço algorítmico da década de 1990Nenhum progresso substancial foi feito nesta área por décadas, pelo menos não em termos de algoritmos que podem resolver gráficos dinâmicos (em mudança).

Avançado até o ano passado, os cientistas da computação Jacob Holm, da Universidade de Copenhagen e Eva Rotenberg, da Universidade Técnica da Dinamarca, abandonaram o problema.

“Já havíamos desistido de pegar a última peça e de resolver o enigma.” Holm diz. “Achamos que ainda haveria mais cinco anos de trabalho, no máximo, antes que pudéssemos resolver o quebra-cabeça.”

Nessa época, quase por acaso, eles perceberam que já haviam resolvido efetivamente a maior parte do problema em outro artigo de pesquisa: um trabalho pré-impresso sobre conceitos planos relacionados, que o casal estreou on-line em 2019.

Com a solução secreta já publicada, o casal foi eliminado nas semanas seguintes, escrevendo uma prova formal de seu aprimoramento no algoritmo gráfico, que não by way of melhorias desde os anos 1990.

“Estamos trabalhando no artigo sem parar, por cinco a seis semanas. E ele acabou enchendo mais de 80 páginas.” Rotenberg diz.

Os resultados, agora publicado, fornece um algoritmo que leva menos tempo computacional para resolver a questão de se um gráfico dinâmico, sujeito a inserções e exclusões de arestas que conectam seus vértices, pode suportar incorporação plana. (Em termos simples, se pudesse ser desenhado em um pedaço de papel sem criar linhas.)

É um grande avanço, pois as mesmas dificuldades surgem em algo tão conceitualmente simples como o problema das três utilidades, que se tornam muito mais insondáveis ​​em campos como o projeto de microchip ou o planejamento de estradas, onde existem muitos mais vértices do que apenas três casas e três serviços.

“Acontece que, para problemas de gráficos dinâmicos, muitas vezes é possível construir alguma estrutura de dados que pode ser usada para contar a resposta após cada mudança no gráfico muito mais rápido do que calcular a resposta do zero”, Holms explica.

“Este resultado é, obviamente, uma grande vitória pessoal para nós.”

As descobertas são anotadas em ESTOQUE 2020: Procedimentos do 52º Simpósio Anual ACM SIGACT sobre Teoria da Computação.

Este artigo foi reescrito, traduzido de uma publicação em inglês. Clique aqui para acessar a matéria original (em inglês)!