NENHUM ALGORITMO CONSEGUE RECONHECER CERTAS FORMAS QUADRIDIMENSIONAIS

Algumas perguntas não têm receita. Não porque ninguém a encontrou ainda, mas porque está provado que nenhum algoritmo — nenhum procedimento passo a passo, por mais longo que seja, executado em qualquer computador — consegue respondê-las corretamente todas as vezes. Cameron McA. Gordon, da Universidade do Texas em Austin, acrescenta duas perguntas desse tipo sobre formas quadridimensionais.

É a mesma forma?

Os matemáticos chamam essas formas de 4-variedades: espaços que, vistos de perto, se parecem em toda parte com o espaço quadridimensional comum. Para entregá-las a um computador, o artigo supõe que elas são construídas a partir de peças planas coladas umas às outras (“linear por partes”, ou PL), de modo que cada uma possa ser descrita por uma lista finita de dados. A pergunta básica é então: dadas duas formas assim, elas são a mesma, a menos de deformação contínua?

Em 1958, A. A. Markov mostrou que essa pergunta não tem algoritmo. A prova de Markov transforma o problema das formas num problema sobre grupos: existem grupos, definidos por um número finito de regras, para os quais nenhum algoritmo consegue decidir se uma dada combinação de seus elementos é igual à identidade — o “problema da palavra”. A partir de um grupo assim, é possível construir formas que um algoritmo só conseguiria distinguir resolvendo esse problema impossível.

Contagem regressiva até sete

O argumento de Markov chega a localizar a dificuldade em formas específicas. Tome S², a superfície de uma bola comum, e forme o produto S² × S², uma forma quadridimensional. Cole k cópias dela umas às outras (uma “soma conexa”, escrita #k). Para algum k, nenhum algoritmo consegue decidir se uma dada forma é #k(S² × S²). Qual k?

O artigo refaz a contagem regressiva. Um grupo com problema da palavra insolúvel e 12 regras, encontrado por Borisov em 1969, deu 14 cópias. Gordon baixou para 12 em 2022. M. Tancer encontrou um novo caminho, pela classificação de Freedman das formas quadridimensionais, e chegou a 9 na versão “topológica”, em que as formas não precisam ser construídas a partir de peças planas. Uma versão anterior deste trabalho chegou a 8. Depois, Kegel, Li e Ren construíram um grupo insolúvel muito menor — 3 geradores e 9 regras —, chegando a 7 na versão topológica e a 9 na versão de peças planas.

Gordon faz o caminho de Tancer funcionar também para formas construídas a partir de peças planas, e prova:

Não existe algoritmo para decidir se uma dada 4-variedade é a mesma, peça por peça, que a soma conexa de 7 cópias de S² × S².

O núcleo da prova é um dicionário. Para cada palavra w no grupo de Kegel, Li e Ren, Gordon constrói uma forma quadridimensional. Se w é igual à identidade, uma sequência de movimentos permitidos sobre as regras — os movimentos de Andrews-Curtis, que reescrevem a descrição sem mudar a forma — mostra que a forma é exatamente sete cópias de S² × S². Se não é, a forma contém laços que não podem ser apertados até um ponto — o que nunca acontece em sete cópias de S² × S² —, então ela não pode ser essas sete cópias. Um algoritmo que reconhecesse #7(S² × S²) resolveria, portanto, o problema da palavra, o que é impossível.

Esferas atadas

A segunda pergunta é sobre nós. Um nó comum é um círculo amarrado no espaço tridimensional, e decidir se um nó pode ser desfeito é possível: existe um algoritmo, devido a Haken. Uma dimensão acima, uma esfera bidimensional pode estar atada dentro do espaço quadridimensional. Em dimensões mais altas, sabe-se que o problema correspondente não tem algoritmo. Para esferas bidimensionais na esfera quadridimensional S⁴, ninguém sabe.

Gordon prova que, dentro de #7(S² × S²), não existe algoritmo para decidir se uma esfera bidimensional — ou qualquer superfície, orientável ou não — está desatada. Pelo caminho, o artigo constrói nessa forma uma esfera cujo espaço ao redor tem um grupo com problema da palavra insolúvel e, em 12 cópias de S² × S², uma esfera cujo grupo contém uma cópia de todo grupo que pode ser descrito por um computador.

O prêmio: zero cópias

O artigo enuncia o objetivo com clareza: baixar o número de cópias até zero. Zero cópias significa a própria esfera quadridimensional S⁴. Em cinco dimensões ou mais, nenhum algoritmo consegue reconhecer a esfera; em duas e três dimensões, um algoritmo consegue. Quatro dimensões continuam em aberto — assim como a questão de saber se esferas atadas em S⁴ podem ser detectadas. Cada cópia removida aproxima as duas perguntas da solução.