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.
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.
Fonte: El Pais
0 Comments:
Postar um comentário