Um problema que parece fácil produz números grandes demais para o nosso universo | Revista Quanta

Não é sempre que crianças de 5 anos conseguem compreender questões nas fronteiras da ciência da computação, mas isso pode acontecer. Suponha, por exemplo, que uma aluna do jardim de infância chamada Alice tenha duas maçãs, mas prefira laranjas. Felizmente, os seus colegas de turma desenvolveram um sistema saudável de comércio de fruta com taxas de câmbio rigorosamente aplicadas: desista de uma maçã, digamos, e poderá obter uma banana. Será que Alice consegue executar uma série de negociações, colhendo e descarregando bananas ou melões, que a levem até sua fruta favorita?

Parece bastante simples. “Você pode ir para a escola primária e contar [isso] às crianças”, disse Christoph Haase, cientista da computação da Universidade de Oxford. “As pessoas vão pensar: 'Isso deve ser fácil.'”

Mas o problema matemático subjacente ao dilema de Alice – chamado problema de acessibilidade para sistemas de adição de vetores – é surpreendentemente sutil. Embora alguns casos possam ser resolvidos facilmente, os cientistas da computação lutaram durante quase meio século para desenvolver uma compreensão abrangente do problema. Agora, numa série de avanços ao longo dos últimos anos, estabeleceram firmemente quão complexo esse problema pode tornar-se.

Acontece que esse problema infantil é absurdamente complexo, quase como um desenho animado - tão complexo que praticamente todos os outros problemas computacionais notoriamente difíceis parece, bem, brincadeira de criança. Tente quantificar o esforço necessário para resolver esse problema e logo você se deparará com números tão grandes que até mesmo contar seus dígitos o levará a alcançar números dos quais nunca ouviu falar. Esses números muitas vezes convidam a comparações com a escala do universo, mas mesmo essas analogias são insuficientes. “Isso não faria justiça”, disse Georg Zetzsche, cientista da computação do Instituto Max Planck de Sistemas de Software em Kaiserslautern, Alemanha. “O universo é tão pequeno.”

Dentro do alcance?

Resumido à sua essência, o problema de acessibilidade trata de objetos matemáticos chamados vetores, que são listas ordenadas de números. As entradas nessas listas são chamadas de componentes, e o número de componentes em um vetor é chamado de dimensionalidade. O inventário de frutas de Alice, por exemplo, pode ser descrito por um vetor quadridimensional (a, b, c, d), cujos componentes representam quantas maçãs, bananas, melões e laranjas ela tem em um determinado momento.

Um sistema de adição de vetores, ou VAS, é uma coleção de vetores que representam as possíveis transições entre estados em um sistema. Para Alice, o vetor de transição (−1, −1, 1, 0) representaria a troca de uma maçã e uma banana por um melão. O problema de acessibilidade VAS pergunta se existe alguma combinação de transições permitidas que possa levá-lo de um estado inicial específico para um estado alvo específico – ou, em termos matemáticos, se existe alguma soma de vetores de transição que transforme o vetor inicial no vetor alvo. Só há um problema: nenhum componente do vetor que descreve o estado do sistema pode cair abaixo de zero.

“Essa é uma restrição muito natural para um modelo de realidade”, disse Wojciech Czerwiński, cientista da computação da Universidade de Varsóvia. “Você não pode ter um número negativo de maçãs.”

Em alguns sistemas, é fácil determinar se o vetor alvo é alcançável. Mas nem sempre é esse o caso. Os cientistas da computação estão mais interessados ​​em sistemas de adição de vetores de aparência simples, nos quais não é óbvio quão difícil é determinar a acessibilidade. Para estudar esses casos, os pesquisadores começam definindo um número que quantifica o tamanho de um determinado sistema. Este número, representado por n, abrange o número de dimensões, o número de transições e outros fatores. Eles então perguntam com que rapidez a dificuldade do problema de acessibilidade pode aumentar à medida que n fica maior.

Para responder a essa pergunta, os pesquisadores usam duas abordagens complementares. Primeiro, eles procuram exemplos de sistemas de adição de vetores particularmente complicados, nos quais a determinação da acessibilidade requer um nível mínimo de esforço. Esses níveis mínimos são chamados de “limites inferiores” na complexidade do problema – eles dizem aos pesquisadores: “Os sistemas mais complicados para um determinado n são pelo menos tão difíceis.

Em segundo lugar, os investigadores tentam estabelecer “limites superiores” – limites sobre o quão difícil pode ser a acessibilidade, mesmo nos sistemas mais diabólicos. Estes dizem: “Os casos mais complicados para um determinado n são no máximo tão difíceis.” Para determinar com precisão o quão difícil é a acessibilidade nos sistemas mais complicados, os pesquisadores tentam empurrar os limites inferiores para cima e os limites superiores para baixo até que se encontrem.

A matéria dos pesadelos

Os sistemas de adição de vetores têm uma longa história. Desde a década de 1960, os cientistas da computação os utilizam para modelar programas que dividem uma computação em muitas partes pequenas e trabalham nessas partes simultaneamente. Este tipo de “computação simultânea” é agora omnipresente, mas os investigadores ainda não compreendem completamente os seus fundamentos matemáticos.

Em 1976, o cientista da computação Richard Lipton deu o primeiro passo para compreender a complexidade do problema de acessibilidade do VAS. Ele desenvolveu um procedimento para construir sistemas em que a maneira mais rápida de determinar se um estado é alcançável a partir de outro é mapear uma sequência de transições entre eles. Isso lhe permitiu usar o comprimento do caminho mais curto entre dois estados cuidadosamente escolhidos como medida da dificuldade do problema de acessibilidade.

Lipton então provou ele poderia construir um sistema de tamanho n em que o caminho mais curto entre dois estados envolveu mais de $latex 2^{2^n}$ transições. Isso implicou um limite inferior exponencial duplo correspondente no esforço necessário para determinar a acessibilidade em seus sistemas. Foi uma descoberta surpreendente – o crescimento exponencial duplo é a matéria dos pesadelos dos cientistas da computação. Na verdade, os investigadores muitas vezes recusam mesmo o crescimento exponencial normal, o que não é nada em comparação: $latex {2^5}= 32$, mas $latex 2^{2^5}$ é superior a 4 mil milhões.

A maioria dos pesquisadores pensava que Lipton havia inventado os sistemas de adição de vetores mais complexos possíveis, o que significa que ele elevou o limite inferior o mais alto possível. A única coisa que faltaria, nesse caso, seria um limite superior – isto é, uma prova de que não poderia haver nenhum sistema em que determinar a acessibilidade fosse ainda mais difícil. Mas ninguém sabia como provar isso. O cientista da computação Ernst Mayr chegou mais perto quando provou em 1981 que é sempre possível, em princípio, determinar a alcançabilidade em qualquer sistema de adição de vetores. Mas a sua prova não estabeleceu qualquer limite quantitativo sobre a dificuldade do problema. Havia um chão, mas nenhum teto à vista.

“Eu certamente pensei sobre isso de vez em quando”, disse Lipton. “Mas depois de um tempo desisti e, pelo que pude perceber, ninguém fez nenhum progresso durante cerca de 40 anos.”

Em 2015, os cientistas da computação Jérôme Leroux e Silvana Schmitz finalmente estabelecido um limite superior quantitativo – tão alto que os investigadores presumiram que era apenas um primeiro passo que poderia ser empurrado para baixo para atingir o limite inferior de Lipton.

Mas não foi isso que aconteceu. Em 2019, os investigadores descobriram um limite inferior muito superior ao de Lipton, subvertendo décadas de sabedoria convencional. O problema de acessibilidade do VAS era muito mais complexo do que se imaginava.

Uma Torre de Poderes

O resultado chocante de 2019 surgiu do fracasso. Em 2018, Czerwiński refutou uma conjectura, de Leroux e Filip Mazowiecki, um cientista da computação atualmente na Universidade de Varsóvia, que teria ajudado a progredir em um problema relacionado. Nas discussões subsequentes, os investigadores encontraram uma nova forma promissora de construir sistemas extra-complexos de adição de vectores, o que poderia implicar um novo limite inferior no problema de acessibilidade do VAS, onde o progresso tinha estagnado durante tanto tempo.

“Na minha cabeça, tudo estava relacionado à acessibilidade do VAS”, lembrou Czerwiński. Durante um semestre com carga letiva leve, ele decidiu focar exclusivamente nesse problema, junto com Leroux, Mazowiecki e outros dois pesquisadores — Sławomir Lasota da Universidade de Varsóvia e Ranko Lazić da Universidade de Warwick.

Depois de alguns meses, seus esforços foram recompensados. Czerwiński e seus colegas demonstraram que eles poderiam construir sistemas de adição de vetores nos quais o caminho mais curto entre dois estados estivesse relacionado ao tamanho do sistema por uma operação matemática chamada tetração, que faz com que até mesmo o pesadelo do crescimento exponencial duplo pareça inofensivo.

A tetração é uma extensão direta de um padrão que conecta as operações mais familiares da matemática, começando com a adição. Adicionar n cópias de um número, e o resultado é equivalente a multiplicar esse número por n. Se você multiplicar juntos n cópias de um número, isso equivale à exponenciação, ou elevar o número ao no poder. A tetração, muitas vezes representada por um par de setas apontando para cima, é o próximo passo nesta sequência: Tetratar um número por n significa exponenciar isso n vezes para produzir uma torre de poderes n histórias altas.

É difícil entender a rapidez com que a tetração sai do controle: $latex 2 uparrowuparrow 3$, ou $latex 2^{2^2}$, é 16, $latex 2 uparrowuparrow 4$ é pouco mais de 65,000, e $latex 2 uparrowuparrow 5$ é um número com quase 20,000 dígitos. É fisicamente impossível escrever todos os dígitos de $latex 2 uparrowuparrow 6$ – uma desvantagem de viver em um universo tão pequeno.

No seu resultado marcante, Czerwiński e os seus colegas provaram que existem sistemas de adição de vectores de tamanho n onde a melhor maneira de determinar a acessibilidade é mapear um caminho envolvendo mais de $latex 2 uparrowuparrow n$ transições, implicando um novo limite inferior que superou o de Lipton. Mas por mais estonteante que seja, a tetração ainda não foi a palavra final sobre a complexidade do problema.

Para Quinquagintillion e além 

Apenas alguns meses após o novo e chocante limite inferior da complexidade da acessibilidade do VAS, Leroux e Schmitz empurrado para baixo o limite superior que haviam estabelecido três anos antes, mas não chegaram até a tetração. Em vez disso, provaram que a complexidade do problema de acessibilidade não pode crescer mais rapidamente do que uma monstruosidade matemática chamada função de Ackermann.

Para compreender essa função, leve o padrão usado para definir a tetração até a sua conclusão sombria. A próxima operação na sequência, chamada pentação, representa tetração repetida; é seguido por outra operação (hexação) para pentação repetida e assim por diante.

A função de Ackermann, denotada $latex A(n)$, é o que você obtém quando sobe um degrau nesta escada de operações com cada parada na reta numérica: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $látex A(3) = 3^3$, $látex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$ e assim por diante. O número de dígitos em $latex A(4)$ é em si um número colossal aproximadamente igual a 1 quinquagintilhão - esse é o nome caprichoso e raramente necessário para um 1 seguido por 153 zeros. “Não se preocupe com Ackermann de 5”, aconselhou Javier Esparza, cientista da computação da Universidade Técnica de Munique.

O resultado de Leroux e Schmitz deixou uma grande lacuna entre os limites inferior e superior – a complexidade precisa do problema de acessibilidade do VAS poderia estar no extremo do intervalo ou em qualquer ponto intermediário. Czerwiński não pretendia deixar essa lacuna permanecer. “Continuamos trabalhando nisso porque estava claro que era a maior coisa que já fizemos em nossas vidas”, disse ele.

O avanço final veio em 2021, enquanto Czerwiński aconselhava um estudante do segundo ano chamado Łukasz Orlikowski. Ele atribuiu a Orlikowski uma variante simples do problema para mantê-lo atualizado, e o trabalho de Orlikowski ajudou os dois a desenvolver uma nova técnica que também se aplicava ao problema de acessibilidade geral. Isso lhes permitiu aumentar o limite inferior substancialmente - até o limite superior de Ackermann de Leroux e Schmitz. Trabalhando de forma independente, Leroux obteve um resultado equivalente ao mesmo tempo.

Finalmente, os pesquisadores identificaram a verdadeira complexidade do problema de acessibilidade. O limite inferior de Czerwiński, Orlikowski e Leroux mostrou que há uma sequência de sistemas de adição de vetores progressivamente maiores nos quais o caminho mais curto entre dois estados cresce em proporção à função de Ackermann. O limite superior de Leroux e Schmitz mostrou que o problema da acessibilidade não pode ser mais complexo do que isso – pouco consolo para quem espera um procedimento prático infalível para resolvê-lo. É uma ilustração impressionante de quão sutis podem ser problemas computacionais aparentemente simples.

nunca terminou

Os pesquisadores continuaram a estudar o problema de acessibilidade do VAS após determinar sua complexidade exata, já que muitas variantes da questão permanecem sem resposta. Os limites superior e inferior de Ackermann, por exemplo, não distinguem entre as diferentes formas de aumentar n, como aumentar a dimensionalidade dos vetores ou aumentar o número de transições permitidas.

Recentemente, Czerwiński e os seus colegas fez progresso separando esses efeitos distintos, estudando a rapidez com que a complexidade pode aumentar em variantes de sistemas de adição de vetores com dimensionalidade fixa. Mas ainda há mais a ser feito – mesmo em três dimensões, onde os sistemas de adição de vetores são fáceis de visualizar, a complexidade exata do problema de acessibilidade permanece desconhecida.

“De certa forma, é simplesmente constrangedor para nós”, disse Mazowiecki.

Os pesquisadores esperam que uma melhor compreensão de casos relativamente simples os ajude a desenvolver novas ferramentas para estudar outros modelos de computação que sejam mais elaborados do que os sistemas de adição de vetores. Atualmente não sabemos quase nada sobre esses modelos mais elaborados.

“Vejo isso como parte de uma busca fundamental para entender a computabilidade”, disse Zetzsche.

Quanta está realizando uma série de pesquisas para melhor atender nosso público. Pegue nosso pesquisa com leitores de ciência da computação e você estará inscrito para ganhar de graça Quanta mercadoria.