Esse matemático resolveu um problema que intrigou os cientistas da computação por 30 anos

Por , em 29.12.2019

Depois de 30 anos sem haver uma solução, o matemático Hao Huang da Universidade Emory (EUA) finalmente desvendou um problema conhecido como “conjetura de sensibilidade”.

A resolução, que contém seis páginas, “mostra que as pessoas ainda podem encontrar provas simples para perguntas profundas e abertas”, explicou Cris Moore, cientista da computação e matemático do Instituto Santa Fe (EUA).

A conjetura de sensibilidade

Grosso modo, a conjetura de sensibilidade afirma que podemos alterar o input para uma determinada função sem alterar seu output.

Ela refere-se a estruturas matemáticas chamadas de funções booleanas, que convertem várias entradas binárias – 0s e 1s, ou “verdadeiros” e “falsos”, por exemplo – em uma única saída binária. Por exemplo, você pode jogar uma moeda 10 vezes e definir uma função booleana para emitir um “1” se você receber pelo menos uma cara e um “0” caso contrário.

Pode parecer abstrato, mas essas funções são essenciais em diversas tecnologias. Como os transistores, que são basicamente botões de liga/desliga com apenas um de dois valores.

Acontece que os cientistas da computação queriam saber mais sobre a complexidade dessas funções. Por exemplo, em uma determinada etapa da função, quantas entradas (input) você precisaria ativar para alterar a saída (output)?

A resposta numérica para essa pergunta – que pode ser estendida a toda a função – é chamada de sensibilidade.

A solução

Depois de alguns anos trabalhando ocasionalmente no problema, Huang finalmente o resolveu no último mês de junho, enquanto estava em Madrid.

Como outros matemáticos antes dele, a abordagem de Huang foi procurar a forma mais natural de trabalhar com as entradas binárias de funções booleanas – tratando-as como pontos de coordenadas, no caso, os cantos de um tipo imaginário de cubo de alta dimensão.

27 anos atrás, uma dupla de matemático e cientista da computação mostrou que, se alguém pegasse pelo menos metade desses pontos e pudesse encontrar conexões entre eles, poderia então provar a conjetura de sensibilidade.

Foi o que Huang fez, escrevendo em seguida sua prova (uma demonstração de duas páginas e quatro de contexto) em um elegante artigo postado online.

Matemática x ciência da computação

De acordo com Huang, não é nenhuma surpresa que um matemático tenha solucionado esse problema da ciência da computação.

“A ciência da computação teórica é matemática abstrata. Os cientistas da computação geralmente precisam que os problemas tenham aplicações, mas nós matemáticos nos preocupamos com a elegância e se o problema pode ser bem definido”, disse. [DiscoverMagazine]

1 Star2 Stars3 Stars4 Stars5 Stars (29 votos, média: 4,97 de 5)

Deixe seu comentário!