Pesquisadores de ciência da computação da Universidade de Copenhagen e da Universidade Técnica da Dinamarca (DTU) achavam que estavam a cinco anos de resolver um enigma matemático da década de 1980. Na realidade, e sem saber, eles quase resolveram o problema e revelaram grande parte da solução em um artigo de pesquisa. A solução poderia ser usada para melhorar os telefones e computadores de amanhã.

Jacob Holm e Eva Rotenberg

Um verdadeiro quebra-cabeças. É assim que se pode descrever com segurança esse problema matemático na disciplina de teoria dos grafos. Dois matemáticos do Departamento de Ciência da Computação da Universidade de Copenhagen e da DTU resolveram um problema contra o qual os mais rápidos e mais inteligentes do mundo têm lutado desde os anos 80.

Os dois cientistas da computação, O professor assistente Jacob Holm da UCPH e a professora associada Eva Rotenberg da DTU quase entregaram sua solução no verão de 2019, depois de enviar um artigo de pesquisa que se tornou o precursor do artigo no qual eles finalmente resolveram o enigma matemático.

"Quase desistimos de pegar a última peça e resolver o enigma. Achamos que tínhamos um resultado menor, um que foi interessante, mas de forma alguma resolveu o problema. Adivinhamos que haveria mais cinco anos de trabalho, no melhor, antes de sermos capazes de resolver o quebra-cabeça, "explica Jacob Holm, quem faz parte do BARC, a seção de algoritmo do Departamento de Ciência da Computação da UCPH.

O problema dos três utilitários

Em 1913, um precursor do enigma matemático agora resolvido foi publicado em The Strand Magazine como "O problema dos três utilitários". Isso fez com que os leitores da revista coçassem a cabeça e ponderassem. No problema, cada um dos três chalés deve ter água, gás e eletricidade, enquanto as "linhas" entre as casas e a água, eletricidade e gás não podem se cruzar - o que não é possível.

Uma solução nas entrelinhas

Simplificando, o quebra-cabeça é sobre como conectar vários pontos em um gráfico sem permitir que as linhas que os conectam se cruzem. E como, com um cálculo matemático - um algoritmo - você pode fazer alterações em uma extensa "rede de gráficos" para garantir que nenhuma linha se cruze sem ter que começar tudo de novo. Propriedades que podem ser usadas para, entre outras coisas, construindo imensas redes rodoviárias ou minúsculas entranhas de computadores, onde os circuitos elétricos nas placas de circuito não podem se cruzar.

Jacob Holm está interessado no enigma matemático desde 1998, mas a resposta só foi revelada enquanto os dois pesquisadores liam seu artigo de pesquisa já submetido. Enquanto isso, os pesquisadores ouviram sobre uma nova técnica matemática que perceberam que poderia ser aplicada ao problema.

"Ao ler nosso artigo de pesquisa, de repente percebemos que a solução estava diante de nossos olhos. Nossa próxima reação foi 'ah, não - atiramos no próprio pé e demos a solução, 'diz a Professora Associada Eva Rotenberg da DTU.

Sobre a teoria dos grafos

Um gráfico é uma construção muito simples usada para modelar coisas que podem ser descritas como objetos e as conexões entre eles. A teoria dos grafos é uma área da matemática e uma ferramenta importante na ciência da computação.

Nesse contexto, um gráfico pode ser ilustrado por um diagrama que consiste em uma série de pontos (nós, vértices) associados a várias linhas (arestas). Cada aresta é ilustrada como uma linha (ou peça curva) com nós como seus dois pontos finais.

Sobre a solução

Existem dois tipos de atualizações em gráficos dinâmicos:Um pode excluir uma aresta e você pode inserir uma nova aresta. Essas duas operações devem ser feitas pelo usuário, enquanto um algoritmo acompanha o desenho da rede o tempo todo. Este é o algoritmo para o qual os pesquisadores encontraram a receita.

Pode ser usado para eletrônicos de computador

Foi quando os dois pesquisadores começaram a escrever o artigo de pesquisa e amarrar pontas soltas para resolver o enigma em que Holm vinha trabalhando intermitentemente desde 1998.

"Trabalhamos no artigo sem parar, por cinco a seis semanas. E, acabou enchendo mais de 80 páginas, "diz Eva Rotenberg.

Felizmente, ninguém os venceu na solução e os dois pesquisadores puderam apresentar seus resultados nas principais conferências teóricas de ciência da computação, que deveriam acontecer em Chicago, mas acabou sendo detido virtualmente.

Então, para que pode ser usada a solução para este enigma matemático? Os dois pesquisadores não sabem ao certo, mas eles têm algumas sugestões.

"Nossa pesquisa é pesquisa básica, então raramente sabemos para que ele será usado. Desde o começo, achamos aplicativos difíceis de imaginar, "diz Jacob Holm, quem adiciona, "O design de microchips e placas de circuito, encontrado em todos os eletrônicos, pode ser uma área onde nosso resultado acaba sendo usado. Ao desenhar fios em uma placa de circuito, eles nunca devem se cruzar. De outra forma, ocorrerão curtos-circuitos. O mesmo se aplica a microchips, que contém milhões de transistores e para os quais é necessário ter um desenho gráfico. "