ESCOLHER NÚMEROS QUE SOMAM O ALVO, QUASE TÃO RÁPIDO QUANTO LÊ-LOS

Eis um quebra-cabeça que qualquer um pode enunciar. Você tem uma lista de números inteiros — digamos 3, 9, 14, 20 — e um alvo, digamos 23. Dá para escolher alguns deles de modo que somem exatamente o alvo? (Aqui, sim: 3 + 20 ou 9 + 14.) Este é o Subset Sum (problema da soma de subconjuntos), um dos problemas mais fundamentais da ciência da computação. O artigo o descreve como um problema NP-completo fundamental, uma família de problemas conhecida por ser difícil de resolver exatamente.

Há, porém, uma brecha. Se os números não forem grandes demais, algoritmos engenhosos rodam num tempo que depende do seu tamanho. O método clássico, de Bellman em 1957, leva um tempo proporcional à quantidade de números n vezes o alvo t. Desde então, os algoritmos não pararam de melhorar:

• Pisinger (1999): proporcional a n × N, em que N é o maior número;
• Bringmann (2017): aproximadamente n + t;
• várias equipes (2021–2024): aproximadamente n + N^(5/3), depois n + N^(3/2).

O santo graal era um tempo de aproximadamente n + N — não muito mais do que ler a entrada. Pesquisadores da área o chamavam de “o problema em aberto mais crucial” dessa linha de trabalho.

A um fio de cabelo do objetivo

Lin Chen, Yuchen Mao e Guochuan Zhang, da Universidade de Zhejiang, na China, apresentam um algoritmo que roda em tempo n + N^(1+ε), em que ε pode ser qualquer número positivo pequeno fixado de antemão — 0,1, 0,01, 0,001. Ele é determinístico, aceita números negativos e valores repetidos, e vem acompanhado de uma prova matemática. Os autores chamam esse tempo de quase ótimo.

O resultado se estende a vetores: escolher itens de modo que várias somas atinjam seus alvos ao mesmo tempo, com tempo N^(d+ε) para d coordenadas. Isso, por sua vez, responde a parte de uma questão levantada por vários grupos sobre programação inteira — encontrar soluções em números inteiros para sistemas de equações cujas variáveis são limitadas. Duas consequências são desenvolvidas explicitamente: dividir um conjunto de números em duas metades iguais, e repartir tarefas entre duas máquinas idênticas da forma mais equilibrada possível.

Levando os números a uma dimensão mais alta

A ideia-chave é geométrica. Já se sabia que o problema é fácil quando os números são densos e o alvo fica bem dentro do intervalo das somas possíveis. A observação dos autores: um conjunto esparso de números pode parecer denso quando visto numa dimensão mais alta.

O exemplo deles é o conjunto {11, 12, 22, 24}. Escreva 11 e 22 como um passo e dois passos ao longo de um primeiro eixo, e 12 e 24 como um passo e dois passos ao longo de um segundo eixo. As somas possíveis então preenchem todos os pontos de um pequeno quadrado de 4 por 4. Mas achate esse quadrado de volta numa linha — calculando 11x + 12y — e as somas formam sete aglomerados separados, com lacunas entre eles, espalhados entre 0 e 69. As lacunas são uma ilusão da projeção; em duas dimensões, a estrutura é simples.

O algoritmo constrói essas coordenadas de dimensão mais alta para qualquer entrada, usando resultados da combinatória aditiva. Dentro da região “preenchida”, as respostas saem de graça. Só uma faixa estreita perto da borda exige trabalho de verdade, que o algoritmo divide em problemas menores e resolve recursivamente. Cada rodada encolhe drasticamente essa faixa, e só um número constante de novas dimensões é acrescentado.

Como a prova foi construída

O artigo abre com um “aviso sobre IA”. Os autores conceberam eles próprios o caminho principal da prova, apoiando-se em seus trabalhos recentes sobre versões densas e multidimensionais do problema. Depois usaram um modelo de IA, o GPT Astra Ultra, para transformar essas ideias em provas matemáticas completas. Ele empacou em vários lemas, que foram resolvidos com ideias dos autores; uma nota de pesquisa pública documenta as conversas. Uma vez pronto o algoritmo aleatorizado básico, o modelo o estendeu às versões determinísticas e multidimensionais “sem nenhuma orientação dos autores”. O modelo também redigiu o artigo e, escrevem os autores, verificou seus principais resultados com uma prova no assistente de provas Lean 4. Os autores assumem total responsabilidade pelo conteúdo.

Ainda não é a linha de chegada

O expoente é 1 + ε, e não exatamente 1, e as constantes ocultas crescem à medida que ε diminui; a dependência em relação ao número de dimensões não é otimizada. Os próprios autores descrevem o algoritmo como “bastante complexo”. O artigo é teórico: não relata nenhuma implementação nem teste de desempenho.