Home / Ciência e Tecnologia / Desvendando como medir a complexidade dos nós

Desvendando como medir a complexidade dos nós

A dupla manteve seu programa em segundo plano por mais de uma década. Durante esse período, alguns computadores de sua coleção desorganizada sucumbiram ao superaquecimento e até às chamas. “Houve um que realmente emitiu faíscas”, disse Brittenham. “Isso foi divertido.” (Essas máquinas, acrescentou ele, foram “aposentadas com honra”.)

Então, no outono de 2024, um artigo sobre um tentativa fracassada de usar aprendizado de máquina refutar a conjectura da aditividade chamou a atenção de Brittenham e Hermiller. Talvez, pensaram eles, a aprendizagem automática não fosse a melhor abordagem para este problema específico: se existisse um contra-exemplo à conjectura da aditividade, seria “uma agulha num palheiro”, disse Hermiller. “Não é exatamente disso que se trata o aprendizado de máquina. Trata-se de tentar encontrar padrões nas coisas.”

Mas reforçou uma suspeita que a dupla já tinha – de que talvez a sua rede de tênis mais cuidadosamente afiada pudesse encontrar a agulha.

O laço que une

Brittenham e Hermiller perceberam que poderiam usar as sequências de desatamento que descobriram para procurar contra-exemplos potenciais para a conjectura da aditividade.

Imagine novamente que você tem dois nós cujos números de desatamento são 2 e 3 e está tentando desatar a soma da conexão. Após uma mudança de cruzamento, você obtém um novo nó. Se quisermos acreditar na conjectura da aditividade, então o número de desatamento do nó original deveria ser 5, e o deste novo nó deveria ser 4.

Mas e se o número de desatamento desse novo nó já for 3? Isso implica que o nó original pode ser desatado em apenas quatro passos, quebrando a conjectura.

“Conseguimos esses nós intermediários”, disse Brittenham. “O que podemos aprender com eles?”

Ele e Hermiller já tinham a ferramenta perfeita para a ocasião trabalhando em seu conjunto de laptops: o banco de dados que haviam passado a década anterior desenvolvendo, com limites superiores no número de milhares de nós desfeitos.

Os matemáticos começaram a adicionar pares de nós e a trabalhar nas sequências de desatamento de suas somas conectadas. Eles se concentraram em somas conectadas cujos números de desatamento haviam sido aproximados apenas no sentido mais amplo, com uma grande lacuna entre seus valores mais altos e mais baixos possíveis. Mas isso ainda os deixava com uma lista enorme de nós para resolver – “definitivamente na casa das dezenas de milhões e provavelmente na casa das centenas de milhões”, disse Brittenham.

Durante meses, seu programa de computador aplicou mudanças de cruzamento nesses nós e comparou os nós resultantes com aqueles em seu banco de dados. Um dia, no final da primavera, Brittenham verificou os arquivos de saída do programa, como fazia quase todos os dias, para ver se havia surgido algo interessante. Para sua grande surpresa, havia uma linha de texto: “CONNECT SUM BROKEN”. Era uma mensagem que ele e Hermiller codificaram no programa — mas nunca esperaram vê-la de fato.

Ver artigo original (Em Inglês)

Deixe um Comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *