Informática

Suposta inovação disruptiva massacra problema clássico de computação; criptografia pode ser a próxima vítma

Um professor que criou um algoritmo que pode derrubar uma doutrina de ciência da computação deixa especialistas do campo animados.

  • segunda-feira, 16 de novembro de 2015
  • Por Tom Simonite
  • Tradução por Elisa Matté (OPINNO)


Imagem: Na terça-feira, o professor da Universidade de Chicago László Babai apresentou um novo algoritmo que simplifica um longo e difícil problema em ciência da computação.

A reivindicação do professor de ter criado um algoritmo que simplifica drasticamente um dos problemas mais notórios de ciência da computação teórica deixou especialistas preparados para reconsiderar a antiga verdade absoluta de seu campo. Isso também é visto como um lembrete de que avanços algorítmicos semelhantes são possíveis e que poderiam enfraquecer os problemas difíceis de solucionar no coração da criptografia que proteger os segredos digitais do mundo.

Em uma sala de conferências lotada na terça e quinta-feira da semana passada, o professor da Universidade de Chicago László Babai deu as duas primeiras de uma série de três palestras que descrevem sua nova solução para um problema chamado do isomorfismo de grafos. O problema pergunta a um computador se dois gráficos diferentes, no sentido de uma coleção de "nós" conectados em uma rede, como um gráfico social, são de fato diferentes representações de uma mesma coisa.

As palestras de Babai têm causado animação porque o isomorfismo de grafos é conhecido como um problema muito desafiador que se acredita há mais de 30 anos que não está muito longe da classe mais difícil de problemas para computadores resolverem. Se Babai estiver certo, está na verdade muito mais perto da classe de problemas que podem ser resolvidos de forma eficiente por computadores, uma categoria conhecida como P (veja "What Does 'P vs. NP' Mean for the Rest of Us?").

"Isso atraiu a imaginação de todos, porque a melhoria é muito grande", diz Richard Lipton, um professor que trabalha em ciência da computação teórica no Georgia Institute of Technology. "Ele chegou a uma classe muito menor". Depois que o professor associado do MIT Scott Aaronson ouviu falar sobre a reivindicação de Babai, ele blogou que poderia ser "o resultado ciência da computação teórica da década".

Os cientistas da computação medem a dificuldade de um problema olhando para a quantidade de recursos computacionais que um algoritmo precisa para resolver um problema à medida que ele aumenta em comparação ao original. Isomorfismo Gráfico é considerado extremamente difícil porque o algoritmo mais conhecido precisa de exponencialmente mais recursos à medida que o tamanho dos gráficos com os quais ele esta trabalhando aumenta.

Esse algoritmo foi publicado em 1983 por Babai com Eugene Luks, da Universidade de Oregon. Babai afirma que seu novo algoritmo experimenta um aumento muito menos penosamente íngreme em recursos à medida que os gráficos com os quais está trabalhando ficam maiores, dando ao isomorfismo gráfico uma boa queda no grau de dificuldade enfrentada.

Babai recusou um pedido de entrevista dizendo que a publicidade seria inapropriada antes de ele terminar totalmente de descrever seu resultado em um artigo que tenha sido verificado pelos seus pares. Ele disse a um participante animado de sua primeira conversa que a pré-impressão estaria vindo "logo, logo."

Lipton diz que recomenda-se cautela sempre que um avanço é reivindicado sem um artigo completo estar disponível, mas que a reputação de Babai significa que muitas pessoas nesta área de pesquisa acreditam que seu resultado é, provávelmente, real. "Estamos falando de um pesquisador estelar", diz Lipton.

Se os resultados de Babai forem confirmados, não haverá muitas repercussão fora do restrito mundo dos peritos em complexidade computacional. Isomorfismo gráfico pode surgir em algumas situações práticas, por exemplo em pesquisar bases de dados de estruturas moleculares, que podem ser representadas na forma de gráficos. Mas há soluções alternativas a resolver um problema de todas as formas possíveis, como o algoritmo de Babai faz.

Uma descoberta semelhante à que Babai reivindica sobre um problema com complexidade computacional semelhante ao isomorfismo gráfico teria repercussões mais significativas. Conhecido como fatoração - decompor um número em todos os seus fatores - sustenta a criptografia mais utilizada para proteger dados armazenados e informações que se deslocam através da Internet.

O algoritmo mais conhecido para fatoração está atualmente inserido em uma classe de dificuldade semelhante ao isomorfismo gráfico. Fatoração carece de algumas características matemáticas que podem ter ativado o resultado de Babai. Mas Lipton diz que sua reivindicação é um lembrete de que novos algoritmos podem derrubar ortodoxias antigas sobre esses tipos de problemas.

"Se alguém descobre como fazer com que seja muito rápido, mesmo teoricamente, seria muito perturbador para criptógrafos", diz ele. A criptografia existente pode ser decifrada usando um poder de computação significativo se os números usados para semear os algoritmos criptográficos não forem grandes o suficiente. Um avanço algorítmica para fatoração poderia mudar o que é viável para as agências governamentais com acesso a grande poder de computação.

Mesmo se um algoritmo melhor para fatoração não for viável, seria motivo para uma seria reflexão, diz Lipton. "Seria mais difícil de levantar-se na frente de uma sala e dizer: 'Minha criptografia é segura porque usa fatoração'".

Para deixar seu comentário, por favor, regístrate ou efetue seu login

Esqueceu sua senha?

Publicidade

Vídeo

Inovadores com menos de 35 anos Brasil

Mais Vídeos

Informes Especiais

Uma Cura para os Gastos com Saúde

Os gastos com a saúde estão fora de controle. E a inovação em medicamentos, testes e tratamentos é o motivo. Mas e se a tecnologia pudesse ser uma forma de poupar dinheiro ao invés de gastá-lo?

Ganhando Com Dispositivos Móveis

Publicidade
Publicidade