Na ciência da computação, o problema de colorir gráfico é um clássico. Inspirado pelo problema de colorir o mapa, ele pergunta:Dada uma rede de nós conectados por links, qual é o número mínimo de cores que você precisa para colorir cada nó de forma que nenhum link conecte dois da mesma cor? Para um pequeno número de cores e links, procurar uma solução é simples:tente todas as combinações possíveis. Mas à medida que os links aumentam, o problema se torna mais restrito - até que, se houver muitos links e cores insuficientes, nenhuma solução pode existir.

"Então, existem essas fascinantes zonas intermediárias onde provavelmente há uma solução, mas é muito difícil de encontrar - e outro onde provavelmente não existe, mas é difícil provar que não existe, "diz o polímata Cris Moore, professor residente do SFI. Isso significa que algoritmos convencionais de resolução de problemas não podem encontrá-los, ele diz. Se alguém começa com uma coloração aleatória, por exemplo, e começa a inverter as cores dos nós, ele não encontrará uma dessas soluções ocultas.

Em um novo artigo apresentado na Conferência sobre Teoria da Aprendizagem de 2021, Moore e seus colaboradores descrevem uma nova maneira de construir problemas com essas soluções ocultas. O grupo inclui o matemático Jess Banks, um ex-estagiário de graduação e pós-bacharelado SFI que agora está buscando um doutorado. na Universidade da Califórnia-Berkeley.

Eles abordam o problema fazendo o papel de uma espécie de advogado do diabo matemático. Em vez de resolver problemas, eles fazem novos, complicados - com soluções ocultas. “Tiramos o chapéu branco do solucionador, o buscador de soluções, e colocamos o chapéu preto de quem projeta problemas complicados - quase como criptografia, "diz Moore." A solução está oculta. "

Os pesquisadores desenvolveram uma maneira sutil de esconder soluções, disse Moore. E quando eles passam esses problemas para algoritmos de solução de problemas, os algoritmos aparecem vazios. "Se pudermos criar problemas que muitos algoritmos não podem resolver, ou até mesmo dizer se há uma solução, "diz Moore, "então temos fortes evidências de que localizamos a zona onde esses problemas são difíceis."

O artigo inclui um teorema que prova que várias famílias de algoritmos falham em encontrar soluções para esses problemas gerados. Isso significa que os pesquisadores estão mais perto do que nunca de identificar o limite de transição de fase dessa zona "difícil" na qual é difícil encontrar soluções - ou provar que não há nenhuma.

Moore diz que o esforço contínuo para identificar problemas com precisão surgiu de conjecturas na física que perguntam como os sistemas mudam à medida que se tornam mais restritos.

"Nossa aventura, " ele diz, "foi transformar essas conjecturas e cálculos da física em provas matemáticas." E a única maneira de continuar avançando no campo, ele diz, é recorrer aos pontos fortes sobrepostos das ferramentas da matemática, física, e ciência da computação.