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

 na categoria Área Exata Educação Superior, Educação superior, Textos Área Exata Educação Superior

Por Natasha Romanzoti

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 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.

Postagens Recentes

Digite o que procura e aperte a tecla Enter para pesquisar