A Census of New Snake-in-the-Box Records

Resumo Técnico: Um Censo de Novos Registros de Snake-in-the-Box

Definição do Problema
O artigo aborda o problema "snake-in-the-box", formulado originalmente por Kautz em 1958 no contexto de códigos de detecção de erros. O problema busca o caminho induzido (sem cordas) mais longo, denominado "snake" (cobra), dentro do grafo hipercubo $Q_n$. Em $Q_n$, os vértices representam cadeias binárias de comprimento $n$, e as arestas conectam cadeias que diferem em exatamente uma coordenada. Uma snake é definida como uma sequência de vértices distintos onde vértices consecutivos são adjacentes, e nenhum par de vértices não consecutivos é adjacente. O comprimento máximo de tal caminho é denotado por $a(n)$.

O artigo também considera estruturas relacionadas: "coils" (ciclos induzidos em $Q_n$) com comprimento máximo $b(n)$, e "symmetric coils" (ciclos onde a segunda metade do ciclo espelha a primeira via uma operação XOR fixa), com comprimento máximo $c(n)$. Embora os valores exatos para $a(n)$ e $b(n)$ sejam conhecidos para dimensões $n \le 8$, e $c(n)$ seja conhecido para $n \le 7$, o problema permanece sem solução para $n \ge 9$ (e $n \ge 8$ para symmetric coils), onde apenas limites inferiores foram estabelecidos através de várias buscas computacionais.

Metodologia e Abordagem
Os autores empregam esforços computacionais sustentados para buscar snakes, coils e symmetric coils mais longos nas dimensões 9 a 13. O artigo não detalha uma arquitetura algorítmica especificamente nova no texto fornecido, mas posiciona seu trabalho como um avanço sobre métodos anteriores, que incluíram algoritmos genéticos, buscas evolutivas baseadas em população, construções baseadas em permutações e buscas de árvore de Monte Carlo.

A abordagem dos autores foca na geração e verificação de caminhos de comprimento recorde. Eles utilizam uma notação padrão onde uma snake é representada por uma sequência de transição — a lista ordenada de índices de coordenadas de 0 a $n-1$ invertidas ao longo do caminho. Para garantir a validade de seus achados, os autores fornecem um conjunto de dados verificável por computador. Eles também realizam um censo do espaço de soluções, contando o número de snakes inequivalentes encontradas nos comprimentos recorde. A equivalência é determinada pelas simetrias de $Q_n$, que incluem $n!$ permutações de coordenadas, $2^n$ translações (XORing) e reversão de caminho.

Contribuições Principais e Resultados
A principal contribuição do artigo é o estabelecimento de novos limites inferiores para $a(n)$, $b(n)$ e $c(n)$ nas dimensões 9 a 13, superando todos os recordes anteriormente conhecidos.

• Comprimentos de Snake ($a(n)$): Os autores apresentam snakes mais longas que as melhores conhecidas anteriormente em todas as dimensões de 9 a 13.

  • $n=9$: Um novo comprimento de 191 (melhorando o anterior de 190). Os autores identificaram 1.311 snakes inequivalentes deste comprimento.
  • $n=10$: Um novo comprimento de 379 (melhorando o anterior de 376).
  • $n=11$: Um novo comprimento de 746 (melhorando o anterior de 737).
  • $n=12$: Um novo comprimento de 1.476 (melhorando o anterior de 1.465).
  • $n=13$: Um novo comprimento de 2.922 (melhorando o anterior de 2.900).
  • As melhorias variam de +1 a +22 sobre os recordes anteriores.

• Comprimentos de Coil ($b(n)$): O artigo relata limites inferiores melhorados para os coils mais longos nas dimensões 9, 10 e 11, com novos comprimentos de 192, 374 e 732, respectivamente.

• Comprimentos de Symmetric Coil ($c(n)$): Limites inferiores melhorados são fornecidos para as dimensões 10 e 11, com novos comprimentos de 370 e 726.

Os autores fornecem um exemplo concreto de uma snake de comprimento 191 em $Q_9$, listando sua sequência de transição completa. Eles observam que, entre milhões de snakes de comprimento 191 amostradas, exatamente 131 classes de simetria foram encontradas para $n=9$, levando à conjectura de que nenhuma outra classe existe, embora não façam tal afirmação de completude para $n \ge 10$.

Significância e Alegações
O artigo reivindica significância primariamente através do avanço empírico dos limites conhecidos para o problema snake-in-the-box. Ao fornecer snakes que são estritamente mais longas do que quaisquer outras conhecidas anteriormente nas dimensões 9 a 13, os autores estreitaram os limites inferiores para o comprimento máximo possível de caminhos induzidos em hipercubos.

O trabalho serve como um "censo" desses novos recordes, oferecendo um conjunto de dados abrangente que inclui as sequências de transição específicas para todas as snakes distintas de comprimento recorde encontradas. Este conjunto de dados é disponibilizado publicamente em um formato verificável por computador, permitindo a verificação independente dos resultados. Os autores enquadram seu trabalho como uma continuação da linhagem computacional estabelecida por pesquisadores anteriores (como Ace, Echols, Meyerson e outros), expandindo a fronteira do que é computacionalmente alcançável neste problema de otimização combinatória, sem alegar ter resolvido o problema para essas dimensões ou ter provado a otimalidade de seus novos limites.