Conjetura da sensibilidade. Matemático resolveu problema de 30 anos

Na fronteira entre a Matemática e a Ciência da Computação, um matemático conseguiu resolver um problema de 30 anos.

Hao Huang, professor assistente de Matemática na Universidade Emory, em Atlanta, nos Estados Unidos, resolveu um problema de 30 anos, cruzando a área da Matemática com a da Ciência da Computação.

O professor provou a Conjetura da Sensibilidade, teoria que, de forma grosseira, afirma que podemos alterar o input para uma determinada função, sem alterar o output – a isto se chama de sensibilidade.

Segundo o Live Science, desde que os matemáticos propuseram esta teoria pela primeira vez, sem nunca a provar, os cientistas da computação perceberam que a Conjetura da Sensibilidade tem enormes implicações para determinar as formas mais eficientes de processar informação.

O mais impressionante não é o facto de Huang ter conseguido solucionar este problema, mas sim a forma elegante e direta como o fez, segundo especialistas da área. A sua solução ainda não passou a revisão por pares nem foi publicada numa revista científica, mas depois de a ter partilhado na Internet, os seus colegas rapidamente a aceitaram, dando-a como certa.

“Sempre que há algum anúncio deste género, 99% das vezes a solução está errada e é muito difícil que as pessoas de fora consigam avaliar. Este faz parte dos 1% dos casos. Estou muito confiante de que esta solução está correta. Porquê? Porque a li e entendi. Demorei cerca de meia hora”, escreveu no seu blogue Scott Aaronson, cientista de computação da Universidade do Texas, em Austin.

Ryan O’Donnell, professor de ciência da computação que estuda teoria dos números na Universidade Carnegie Mellon, em Pittsburgh, afirmou que a solução de Huang pode ser resumida num único tweet:

Mas, afinal, o que conseguiu provar Huang? Para simplificar, imagine um cubo 3D com lados com 1 unidade de comprimento. Se colocar este cubo num sistema de coordenadas 3D, um canto teria as coordenadas (0,0,0), o seguinte teria (1,0,0), o que se localiza acima dele seria (0,1,0), e assim sucessivamente.

Além disso, conseguimos retirar metade dos cantos (quatro) sem ter nenhum par de vizinhos: (0,0,0), (1,1,0), (1,0,1) e (0,1,1). Podemos comprová-lo observando o cubo, mas também o sabemos porque todos os lados são diferentes.

A Conjetura de Sensibilidade baseia-se em encontrar quantos vizinhos temos quando retiramos mais de metade dos vizinhos de um cubo de dimensão mais alta, ou hipercubo.

As coordenadas de um hipercubo são strings de 1s e 0s, onde o número de dimensões corresponde ao comprimento da string. Para um hipercubo 4D, por exemplo, existem 16 pontos diferentes, o que significa 16 strings diferentes de 1s e 0s com quatro dígitos.

Agora, escolha metade mais 1 pontos individuais no hipercubo – para um hipercubo 4D, isso significa escolher 9 ou 8 + 1 pontos diferentes de um total de 16.

A partir desse conjunto mais pequeno, encontre o ponto com o maior número de vizinhos. Os vizinhos diferem em apenas um número: por exemplo, 1111 e 1110 são vizinhos, porque só precisamos de trocar um dígito para transformar o primeiro no segundo.

Huang provou que este canto deve ter pelo menos tantos vizinhos quanto a raiz quadrada do número de dígitos – neste caso, a raiz quadrada de 4 – que é 2.

O matemático conseguiu chegar a esta conclusão conceptualizando o hipercubo usando matrizes de números em linhas e colunas, uma forma completamente inesperada de manipular uma matriz com um arranjo incomum de -1s e 1s. “Ele usou métodos espectrais, mas de uma maneira completamente nova. É muito misteriosa, mas prova que podemos usar esta técnica mais vezes”, escreveu um matemático.

A solução de Huang é empolgante porque dá mais um passo no campo da Ciência da Computação. No entanto, é também notória pelo facto de ter introduzido um novo método na Matemática.

PARTILHAR

RESPONDER

Borussia Dortmund 1-0 Sporting | Um Mal(en) que veio só… e foi suficiente

O “bicho papão Haaland não jogou, mas nem assim os “leões” conseguiram contrariar o maior poderio germânico. O Sporting saiu de Dortmund com uma derrota, apesar da excelente réplica no Signal Iduna Park, e muito por …

FC Porto 1-5 Liverpool | Dragão atropelado em casa

O Liverpool é uma espécie de “besta” em tons de “red” para o FC Porto. Em nove jogos oficiais, os “azuis-e-brancos” nunca venceram, somando 3 empates e 6 derrotas, a mais recente foi pesadíssima e …

China desenvolve arma invisível capaz de destruir redes de comunicação em dez segundos

Uma equipa de cientistas chineses está a desenvolver uma arma sónica, que gera um intenso pulso eletromagnético, capaz de destruir redes de comunicação e de fornecimento de energia elétrica. A arma poderá ter um alcance …

Dezenas de mulheres abusadas por funcionários da OMS na República Democrática do Congo

Dezenas de mulheres e meninas foram abusadas sexualmente por voluntários da Organização Mundial de Saúde (OMS) destacados para enfrentar o Ébola na República Democrática do Congo (RDC), entre 2018 e 2020, concluiu um inquérito independente …

Evolução de parasita está a tornar mais difícil detetar e tratar a malária

Uma mutação do parasita que causa a malária está a "camuflar" as proteínas que são identificadas nos testes rápidos, tornando mais difícil detetar e tratar a doença. De forma semelhante aos testes à covid-19, baratos e …

Banguecoque em alerta. Mais de 70.000 casas inundadas na Tailândia

As autoridades tailandesas têm feito esforços para proteger partes de Banguecoque das cheias, que já inundaram 70.000 casas e mataram seis pessoas nas províncias no norte e centro do país. A tempestade tropical Dianmu causou cheias …

Exilados sírios obrigados a pagar taxas para evitar o alistamento obrigatório

No início deste ano, Yousef, um sírio de 32 anos que vive na Suécia, teve que pagar as taxas que lhe isentavam da obrigatoriedade de se alistar no exército da Síria, caso contrário a família …

Portugal tem cerca de 8.200 pessoas em situação de sem-abrigo, mais de metade em Lisboa

Estima-se que, em 2020, cerca de 485 pessoas tenham abandonado esta condição, o que representa uma descida de 39% face a 2019. Portugal terá cerca de 8.200 pessoas em situação de sem-abrigo, segundo os resultados de …

Simone Biles: "Deveria ter desistido muito antes dos Jogos Olímpicos"

"Uma mulher preta tem que ser a melhor, as pessoas tentam menosprezar", lamentou a multi-campeã olímpica de ginástica. Simone Biles não conquistou qualquer medalha de ouro nos Jogos Olímpicos deste ano mas foi a atleta mais …

Mãe e filho de 2 anos morrem à porta do estádio. Jogo decorreu normalmente

Queda aconteceu pouco antes de começar um jogo da Major League Baseball, em San Diego. O desporto passou para segundo plano na tarde deste domingo, pouco antes de um jogo de beisebol, nos Estados Unidos da …