Solucionado um famoso problema matemático em duas páginas condensadas em um tuíte
Hao Huang demonstra depois de 30 anos a chamada conjetura da sensibilidade, inserida na teoria da complexidade computacional
Quando um problema matemático importante, proposto há 30 anos, acaba sendo solucionado em duas escassas páginas de raciocínio, só resta dar os parabéns. Como aquela dama sacrificada em um jogo de xadrez que fascina pela criatividade da estratégia, essas duas páginas de inventividade matemática são um presente para qualquer admirador da disciplina. Seu autor, Hao Huang, matemático e teórico da ciência da computação da Universidade Emory (EUA), testou a chamada conjetura de sensibilidade em um artigo de seis páginas (duas de demonstração e o restante para apresentar o contexto e enunciar as consequências e derivadas do resultado), que publicou no início de julho no ArXiV, um arquivo aberto de artigos científicos. Algumas horas depois, as redes sociais já o estavam parabenizando. O influente blog de Gil Kalai, da Universidade Hebraica de Jerusalém, anunciou: "Incrível: Hao Huang demonstra a conjetura de sensibilidade!" Depois de um tempo, Ryan O'Donnell, um pesquisador da Carnegie Mellon, comprimia as duas páginas milagrosas nos 282 caracteres de um tuíte.
A conjetura da sensibilidade foi enunciada por Noam Nisan e Mario Szegedy em 1989, e está inserida na informática teórica, especificamente na teoria da complexidade computacional, com aplicações na teoria da escolha social. Tomar decisões não é uma tarefa fácil. Para tanto, máquinas e humanos dependem de regras de decisão ou algoritmos, isto é, métodos sistemáticos previamente projetados. Suponha que tenhamos de tomar uma decisão binária, sim ou não, com base no resultado de um número (N) de dados, também binários. Por exemplo, poderia ser a aprovação ou não de um texto legal, com base nos votos de um conjunto de eleitores (cada voto seria um dos dados).
Algumas dessas regras de decisão serão mais sensíveis a alterações nos dados do que outras. No exemplo anterior, se a escolha é baseada na opinião da maioria dos eleitores, então, o resultado é sensível a exatamente a metade mais uma das opiniões: se exatamente N/2 + 1 dos eleitores aprovarem o texto, uma mudança de opinião de qualquer um desses eleitores alteraria o resultado. Em geral, uma regra de decisão é considerada sensível para determinados dados se, mudando um deles, se muda a decisão final. O grau de sensibilidade da regra de decisão é o número máximo de dados aos quais a regra pode ser sensível no pior dos casos (ou seja, em casos-limite extremos).
Seguindo o exemplo anterior, se dividirmos os eleitores em K distritos eleitorais iguais e basearmos o resultado da escolha em que pelo menos um dos distritos aprove o texto por consenso, então a sensibilidade da regra de decisão se reduz a N/K, ou a K, o que for maior. De fato, casos limítrofes ocorrem quando exatamente um distrito chega a um consenso, ou quando todos ficam a um voto do consenso. No primeiro caso, somente N/K mudanças de opinião poderiam afetar o resultado, enquanto no segundo, apenas K.
É assim que o grau de sensibilidade de uma regra de decisão pode ser tomado como um barema para determinar sua adequação em determinados processos eleitorais. No entanto, embora em alguns contextos seja bem motivado e fácil de determinar, em outros casos, não. Por exemplo, para avaliar se uma regra de decisão é adequada para ativar ou não um nível de emergência, digamos, um risco de incêndio de uma máquina. Para isso, medições de certos parâmetros são empregadas como dados. Começa-se com a temperatura ambiente; se exceder um certo nível, mede-se o nível de umidade; caso contrário, mede-se o nível de água do radiador. Quanto menos medições forem necessárias, melhor. Nesse caso, avaliamos a adequação da regra de decisão com base na complexidade das perguntas, e esse é outro dos muitos baremas para regras de decisão.
Hao Huang@Emory:
— Ryan O'Donnell (@BooleanAnalysis) July 1, 2019
Ex.1: ∃edge-signing of n-cube with 2^{n-1} eigs each of +/-sqrt(n)
Interlacing=>Any induced subgraph with >2^{n-1} vtcs has max eig >= sqrt(n)
Ex.2: In subgraph, max eig <= max valency, even with signs
Hence [GL92] the Sensitivity Conj, s(f) >= sqrt(deg(f))
Mas, é possível estabelecer alguma relação entre esses baremas? Sabemos que a complexidade das perguntas em uma regra de decisão não pode ser inferior ao seu grau de sensibilidade, isto porque, se alguma das medidas sensíveis permanecer sem resposta, a decisão não poderá ser determinada. Será que, por sua vez, haveria uma relação inversa? É exatamente isso que postula a conjetura da sensibilidade: que, qualquer que seja a regra de decisão, sua complexidade de perguntas é menor que uma potência de seu grau de sensibilidade. Combinada com a observação anterior, a conjetura, agora Teorema, graças a Huang, estabelece que o grau de sensibilidade e a complexidade das questões são, em escala logarítmica, baremas equivalentes.
Em apenas duas páginas de argumentação, Huang demonstra a conjetura baseando-se em resultados prévios que reduziram o problema a um problema sobre subgrafos induzidos do hipercubo N-dimensional. Por sua vez, Huang, que é especialista na teoria espectral de grafos, reduziu o problema a um problema sobre valores próprios de matrizes de signos. O célebre Teorema de Entrelaçamento de Cauchy fez o resto.
Há a circunstância de que Huang estava em Madri quando encontrou a solução (sua mulher estava visitando o ICMAT - Instituto de Ciências Matemáticas). Segundo conta, ele se refugiou em seu quarto de hotel durante a espetacular onda de calor que assolou a Europa no final de junho. Aparentemente, o calor durou apenas o tempo justo e necessário para que Huang pudesse completar, naqueles poucos dias, 30 anos de busca.
Albert Atserias é catedrático de informática teórica da Universidade Politécnica da Catalunha
