Home › Outras

Matemático resolve problema que intrigou os cientistas da computação por 30 anos

Por Natasha Romanzoti, 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).

• Matemático acaba de resolver um problema enganosamente simples que ficou sem resposta por 64 anos

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.

• “Problema dos três corpos”, que atormenta astrônomos desde Newton, é resolvido em menos de um segundo por IA

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.

• Mexicano resolve problema físico que estava há dois mil anos sem solução

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]

Compartilhe:

Curta no Facebook: