p A conjectura de sensibilidade tem se destacado como uma das mais importantes, e desconcertante, problemas abertos na ciência da computação teórica por quase três décadas. Parece que finalmente encontrou seu par por meio do trabalho de Hao Huang, professor assistente de matemática na Emory University. p Huang apresentará uma prova da Conjectura de Sensibilidade durante a Conferência Internacional sobre Estruturas e Algoritmos Aleatórios, definido para Zurique, Suíça, 15 a 19 de julho.

p "Tenho atacado esse problema de vez em quando desde 2012, "Huang diz, "mas a ideia-chave surgiu para mim há cerca de uma semana. Finalmente identifiquei a ferramenta certa para resolvê-la."

p Huang postou a prova em sua página inicial e ela logo gerou burburinho entre matemáticos e cientistas da computação nas redes sociais, que elogiaram sua notável concisão e simplicidade.

p A conjectura de sensibilidade se relaciona a dados booleanos, que mapeia as informações em verdadeiro-falso, ou 1-0 binário. As funções booleanas desempenham um papel importante na teoria da complexidade, bem como na concepção de circuitos e chips para computadores digitais.

p "Na matemática, uma função booleana é um dos assuntos discretos mais básicos - assim como os números, gráficos ou formas geométricas, "Huang explica.

p Existem muitas medidas de complexidade de uma função booleana, e quase todos eles - incluindo a complexidade da árvore de decisão, a complexidade do certificado, a complexidade da consulta aleatória e muitas outras - são conhecidas por serem polinomialmente relacionadas. Contudo, há um caso desconhecido, a chamada sensibilidade de uma função booleana, que mede a sensibilidade da função ao alterar uma entrada de cada vez.

p Em 1994, os matemáticos Noam Nisan e Mario Szegedy propuseram a Conjectura de Sensibilidade a respeito desse caso desconhecido.

p "A conjectura deles diz que a sensibilidade de uma função booleana também está polinomialmente relacionada a outras medidas, "Huang diz." Se for verdade, então deixaria de ser um outlier e se juntaria ao resto deles. "

p Huang desenvolveu um método algébrico para provar a conjectura. "Espero que este método também tenha algum potencial para ser aplicado a outros problemas combinatórios e de complexidade importantes para a ciência da computação, " ele diz.