Navegar

11/01/2023

Na Folha, Viana fala sobre a conjectura da sensibilidade

Reprodução da coluna de Marcelo Viana na Folha de S. Paulo

Função de Boole é o nome que matemáticos e cientistas da computação dão a qualquer regra para transformar dados binários (Sim ou Não) num resultado binário. Um médico, por exemplo, usa esse tipo de raciocínio quando decide receitar ou não um medicamento com base nas respostas a perguntas como “É diabético?”, “É alérgico?” etc. É um conceito crucial em computação, porque tudo o que os computadores fazem é calcular funções de Boole.

A “sensibilidade” da função de Boole é o menor número de mudanças nos dados suficiente para que o resultado seja trocado. É uma medida da complexidade da função. Há outras, mas foi provado que dão resultados parecidos: com a possível exceção da sensibilidade, todas concordam em quais funções de Boole são realmente complicadas (complexidade exponencial) e quais nem tanto (complexidade polinomial).

Leia mais: Confira as oportunidades de trabalho no IMPA
Nina da Hora e Julia Jaccoud integram Programa de Verão
‘Meu sonho era conhecer o IMPA’, diz professor do Pará

Em 1992, Noam Nisan (Israel) e Mario Szegedy (Estados Unidos) conjecturaram que a sensibilidade também deveria concordar com as demais, mas durante quase 30 anos ninguém conseguiu provar esse fato. Até que, em 2019, o jovem pesquisador Hao Huang, da Universidade Emory, nos Estados Unidos, surpreendeu todos com uma solução.

Huang se interessara pela conjectura logo que ouviu falar dela pela primeira vez, em 2012, e manteve o desafio em mente enquanto trabalhava em problemas mais acessíveis. Dez anos antes, Craig Gotsman (Estados Unidos) e Nati Linial (Israel) tinham observado que para resolver o problema bastaria provar uma certa afirmação sobre vértices de cubos em muitas dimensões, mas ninguém sabia fazer isso também.

Até que em 2018 Huang teve a ideia de usar um resultado matemático com mais de 200 anos: o teorema de interligação do francês Augustine Cauchy. Empolgado com essa abordagem, decidiu solicitar uma bolsa da Fundação Nacional da Ciência para ter os meios para se dedicar à tarefa. Num serão no hotel, enquanto escrevia o plano de trabalho para a bolsa, percebeu como transformar a ideia numa prova completa!

O melhor de tudo, a prova de Huang não ocupa nem duas páginas (o trabalho todo tem seis), é de uma clareza cristalina e abre a perspectiva de se provarem outros resultados.

Para ler o texto na íntegra acesse o site do jornal

Leia também: Últimos dias para solicitar apoio de até R$ 20 mil do INCTMat
Serrapilheira e Faperj fazem edital para negros e indígenas