CONJETURA
DA
SENSIBILIDADE:
MATEMÁTICO
RESOLVE
PROBLEMA DE
30 ANOS
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.
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.
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.
Em apenas duas páginas de argumentação,
Huang demonstra a conjeturabaseando-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.
1