Resumo Técnico: Relaxação Analítica de Tempo Polinomial para o Problema do Caixeiro Viajante

Declaração do Problema

O Problema do Caixeiro Viajante (TSP - Travelling Salesman Problem) é identificado como um desafio canônico de otimização combinatória NP-difícil. Soluções exatas tradicionais, como Programação Linear Inteira (ILP) e o algoritmo de programação dinâmica de Held-Karp, exigem a avaliação do espaço de ciclos Hamiltonianos de um grafo ponderado. Esses métodos estão limitados por complexidades computacionais fatoriais $O(N!)$ ou exponenciais $O(N^2 2^N)$, tornando-os impraticáveis para aplicações do mundo real que envolvem instâncias de problema maiores que aproximadamente $N \le 25$.

Metodologia

O artigo propõe uma nova estrutura analítica contínua que mapeia espaços de permutação discretos em um manifesto de tensor de fluxo de probabilidade contínuo. Em vez de percorrer árvores de busca discretas, o método reformula a tarefa de otimização como um problema algébrico de propagação de tensores. A abordagem é regida por três postulados centrais:

1. Incorporação em Manifesto Contínuo: Permutações discretas são incorporadas em um espaço de tensor de fluxo de probabilidade contínuo $P \in \mathbb{R}^{N \times N}$. As probabilidades de transição são definidas por leis de potência de custo inverso, onde a probabilidade $P_{ij}$ é inversamente proporcional aos gradientes de peso das arestas elevados a um parâmetro de escala $\alpha$.
2. Normalização Transcendental e Cumulativa Dependente de Histórico: Para impor restrições Hamiltonianas sem mascaramento exponencial de subconjuntos, as probabilidades dos caminhos são ponderadas dinamicamente. O artigo introduz três formulações analíticas:
   • Abordagem 1 (Fluxo de Probabilidade Padrão): Pontua transições com base na razão entre probabilidade e custo da aresta.
   • Abordagem 2 (Heurística Pi-Exponencial): Aplica uma escala transcendental usando $\pi$ aos valores de probabilidade.
   • Abordagem 3 (Relaxação Transcendental HK): Utiliza um fator de matriz estático pré-calculado $\gamma(N) = \pi^{(N^2 / 2^N)}$.
3. Truncamento de Série Espectral: O permanente intratável de coberturas de ciclos é aproximado usando expansões de série de Maclaurin truncadas da função geradora exponencial de matriz $e^{tW}$. Isso reduz a extração de coeficientes para limites de multiplicação de matrizes polinomiais, especificamente $O(N)$.

O algoritmo resultante opera em três fases: Inicialização do Tensor, Construção do Tensor de Transição e Propagação de Estado Sequencial. Ele executa $N$ etapas para avaliar nós não visitados, selecionando o score de custo-para-probabilidade mínimo, alcançando um tempo de execução determinístico estrito de $O(N^3)$.

Principais Contribuições

• Mudança Algorítmica: Um algoritmo determinístico que evita a enumeração exponencial de subconjuntos ao utilizar matrizes estocásticas, fatores de escala transcendentais e séries de Maclaurin truncadas.
• Redução de Complexidade: Redução teórica da geração de tours de TSP de tempo exponencial para tempo polinomial estrito de $O(N^3)$.
• Implementação: Provisão de implementações de código tanto em Python (NumPy) quanto em Java, demonstrando a viabilidade da abordagem de propagação de tensor.
• Escalabilidade: Demonstração de escalabilidade estável para topologias de grafos de escala empresarial, com tempos de execução permanecendo baixos mesmo conforme $N$ aumenta.

Resultados

O artigo apresenta resultados de benchmarks abrangentes para tamanhos de problema $N = 1$ a $100$, comparando as abordagens analíticas propostas contra baselines exatos de Held-Karp.

• Tempo de Execução: O método $O(N^3)$ proposto demonstra tempos de execução significativamente mais rápidos comparados ao Held-Karp. Para $N=20$, o método proposto leva 0,205 ms, enquanto o Held-Karp requer 870.000 ms. Para $N=100$, o método proposto completa em 15,80 ms, enquanto o Held-Karp é observado como exigindo buscas de "Static-Array" (implicando que o método exponencial é inviável).
• Qualidade da Solução: Os custos de tour gerados pelas abordagens propostas são relatados como alinhando-se empiricamente com as baselines ótimas conhecidas.
  • Abordagem 1 e Abordagem 3: Estes métodos produzem custos idênticos à baseline exata de Held-Karp em todas as instâncias testadas ($N=1$ a $100$).
  • Abordagem 2: Este método mostra desvios menores (por exemplo, em $N=6$, o custo é 399,10 vs. 398,50 exato), mas permanece próximo da baseline ótima.
• Escalabilidade de Grande Escala: O artigo inclui projeções para grafos ultra-grandes até $N=10.000$. Estima-se que para $N=10.000$, o algoritmo exigiria aproximadamente $1,00 \times 10^{12}$ FLOPs, 800 MB de memória e um tempo de execução de cerca de 15,80 minutos.

Significância e Alegações

O artigo afirma que, ao reestruturar a otimização combinatória através de tensores algébricos contínuos, escalas transcendentais e aproximações de séries polinomiais, a geração de tours de TSP pode ser executada deterministicamente em tempo polinomial. O autor afirma que este framework permite contornar a enumeração exponencial de subconjuntos enquanto mantém o alinhamento empírico com soluções ótimas.

A significância deste trabalho é apresentada como uma solução potencial para as limitações de escalabilidade dos solvers atuais de TSP, permitindo o tratamento de topologias de grafos de escala empresarial que eram anteriormente restritas a instâncias pequenas. O artigo conclui observando que trabalhos futuros explorarão a aceleração de hardware via núcleos de tensor de GPU para otimizar ainda mais o desempenho para instâncias de grafos esparsos massivos ($N > 10.000$).