Um matemático resolveu um problema de 30 anos na fronteira entre matemática e ciência da computação. Ele usou uma prova inovadora e elegante que deixa seus colegas maravilhados com sua simplicidade.
Hao Huang, professor assistente de matemática da Emory University em Atlanta, provou uma ideia matemática chamada conjectura de sensibilidade, que, em termos incrivelmente grosseiros, afirma sobre o quanto você pode alterar a entrada para uma função sem alterar a saída (isso é a sua sensibilidade).
Nas décadas desde que os matemáticos propuseram pela primeira vez a conjectura de sensibilidade (sem prová-la), os cientistas teóricos da computação perceberam que ela tem enormes implicações para determinar as maneiras mais eficientes de processar informações.
O que é notável na prova de Huang, de acordo com outros especialistas da área, não é apenas o fato de Huang ter conseguido, mas também a maneira elegante e direta em que ele fez isso. Sua prova não foi oficialmente revisada por pares ou publicada em nenhum diário de matemática. Mas logo depois que Huang o colocou online, em 1º de julho, seus colegas o aceitaram rapidamente como fato.
"Sempre que há um anúncio como esse", escreveu o cientista da computação da Universidade do Texas em Austin, Scott Aaronson, em seu blog, "~ 99% das vezes a prova está errada ou, de qualquer forma, é muito complicado para quem o avaliar. rapidamente. Esse é um dos 1% restantes dos casos. Estou bastante confiante de que a prova está correta. Por quê? Porque eu a li e entendi. Demorei cerca de meia hora. "
Ryan O'Donnell, professor de ciência da computação que estuda teoria dos números na Universidade Carnegie Mellon, em Pittsburgh, apontou que a prova de Huang pode ser resumida em um único tweet:
O que Huang realmente provou?
Por uma questão de simplicidade, imagine um cubo 3D com lados com 1 unidade de comprimento. Se você colocar esse cubo em um sistema de coordenadas 3D (o que significa que ele tem medidas em três direções), um canto terá as coordenadas (0,0,0), e o próximo a ele (1,0,0), o um acima pode ser (0,1,0) e assim por diante. Você pode fazer metade dos cantos (quatro cantos) sem ter nenhum par de vizinhos: (0,0,0), (1,1,0), (1,0,1) e (0,1,1) não são ' t vizinhos. Você pode mostrar isso olhando para o cubo, mas também sabemos disso porque todos eles são diferentes em mais de uma coordenada.
A conjectura de sensibilidade é descobrir quantos vizinhos você tem quando ocupa mais da metade dos cantos de um cubo de maior dimensão ou hipercubo, disse o matemático da Universidade Hebraica Gil Kalai. Você pode escrever as coordenadas do hipercubo como cadeias de 1s e 0s, onde o número de dimensões é o comprimento da cadeia, disse Kalai à Live Science. Para um hipercubo 4D, por exemplo, existem 16 pontos diferentes, o que significa 16 cadeias diferentes de 1s e 0s com quatro dígitos.
Agora escolha metade mais 1 ponto individual no hipercubo (para um hipercubo 4D, isso significa escolher nove - ou 8 + 1 - pontos diferentes de um total de 16).
Nesse conjunto menor, encontre o ponto com mais vizinhos - qual é o mínimo número de vizinhos que pode ter? (Os vizinhos diferem em apenas um número. Por exemplo, 1111 e 1110 são vizinhos, porque você só precisa trocar um dígito para transformar o primeiro no segundo.)
Huang provou que esse canto deve ter pelo menos tantos vizinhos quanto a raiz quadrada do número de dígitos - nesse caso, a raiz quadrada de 4 - que é 2.
Para dimensões baixas, você pode dizer que isso é verdade apenas verificando. Não é tão difícil verificar 16 coordenadas no cubo (ou "strings") quanto a vizinhos, por exemplo. Mas toda vez que você adiciona uma dimensão ao cubo, o número de cadeias de caracteres dobra. Portanto, o problema fica mais difícil de verificar rapidamente.
O conjunto de strings com 30 dígitos - as coordenadas para os cantos de um cubo de 30 dimensões - possui mais de 1 bilhão de strings diferentes, o que significa que o cubo tem mais de 1 bilhão de cantos. Com cadeias de caracteres de 200 dígitos, há mais de um novecdilhão. Isso é um milhão de bilhões de bilhões de bilhões de bilhões de bilhões de bilhões, ou 1 seguido por 60 zeros.
É por isso que os matemáticos gostam de provas: eles mostram que algo é verdadeiro em todos os casos, não apenas nos fáceis.
"E se n é igual a um milhão - isso significa que temos cadeias de comprimento 1 milhão -, então a conjectura é que, se você pegar 2 ^ 1.000.000-1 e adicionar 1, haverá uma cadeia com 1.000 vizinhos - a raiz quadrada de um milhão, "Disse Kalai.
O último grande avanço na conjectura de sensibilidade ocorreu em 1988, disse Kalai, quando os pesquisadores provaram que uma corda precisa ter pelo menos o logaritmo de n vizinhos. Esse é um número muito menor; o logaritmo de 1.000.000 é apenas 6. Portanto, a prova de Huang acabou de descobrir que pelo menos 994 outros vizinhos estão lá fora.
Uma prova elegante e "misteriosa"
"É muito misterioso", disse Kalai sobre a prova de Huang. "Ele usa 'métodos espectrais', métodos muito importantes em muitas áreas da matemática. Mas usa métodos espectrais de uma maneira nova. Ainda é misterioso, mas acho que podemos esperar que essa nova maneira de usar métodos espectrais tenha gradualmente mais aplicações ".
Em essência, Huang conceituou o hipercubo usando matrizes de números em linhas e colunas (chamadas matrizes). Huang descobriu uma maneira completamente inesperada de manipular uma matriz com um arranjo incomum de -1s e 1s que "faz tudo dar certo", escreveu Aaronson em seu blog.
Huang "pegou essa matriz e a modificou de uma maneira muito engenhosa e misteriosa", disse Kalai. "É como se você tivesse uma orquestra e eles tocassem alguma música, e então você deixasse que alguns dos músicos ficassem de cabeça para baixo, e a música se tornasse completamente diferente - algo assim".
Essa música diferente acabou sendo a chave para provar a conjectura, disse Kalai. É misterioso, ele disse, porque, embora os matemáticos entendam por que o método funcionou nesse caso, eles não entendem completamente essa nova "música" ou em que outros casos pode ser útil ou interessante.
"Por 30 anos, não houve progresso, e então Hao Huang resolveu esse problema, e encontrou uma prova muito simples de que a resposta é a raiz quadrada de n", Disse Kalai." Mas durante esses 30 anos ... as pessoas perceberam que essa questão é muito importante na teoria da computação. "
A prova de Huang é empolgante porque avança no campo da ciência da computação, disse Kalai. Mas também é digno de nota porque introduziu um novo método, e os matemáticos ainda não sabem ao certo o que mais o novo método de Huang pode permitir que eles realizem.
