Um algoritmo galáctico é um algoritmo com um desempenho teórico (assintótico) que bate recordes, mas que não é utilizado devido a restrições práticas. Os motivos típicos para isso são que os ganhos de desempenho apenas se manifestam em problemas que são tão grandes que nunca chegam a ocorrer, ou a complexidade de implementação do algoritmo supera um ganho relativamente pequeno no desempenho no mundo real. Os algoritmos galácticos foram assim batizados por Richard Lipton e Ken Regan, porque nunca serão usados em quaisquer conjuntos de dados na Terra.

Casos de uso possíveis Mesmo que nunca sejam usados na prática, os algoritmos galácticos ainda podem contribuir para a ciência da computação:

Um algoritmo, mesmo que impraticável, pode demonstrar novas técnicas que poderão, eventualmente, ser usadas para criar algoritmos práticos. Veja, por exemplo, a capacidade de canal de comunicação, abaixo. O poder computacional disponível pode alcançar o ponto de cruzamento (crossover), de modo que um algoritmo anteriormente impraticável se torne prático. Veja, por exemplo, os códigos de verificação de paridade de baixa densidade, abaixo. Um algoritmo impraticável ainda pode demonstrar que os limites conjeturados podem ser alcançados, ou que os limites propostos estão errados, e, consequentemente, avançar a teoria dos algoritmos (veja, por exemplo, o algoritmo de Reingold para conectividade em grafos não direcionados). Como afirma Lipton: Isso por si só poderia ser importante e frequentemente é um ótimo motivo para descobrir tais algoritmos. Por exemplo, se amanhã houvesse uma descoberta que mostrasse que existe um algoritmo de fatoração com um limite de tempo enorme, mas comprovadamente polinomial, isso mudaria as nossas crenças sobre a fatoração. O algoritmo poderia nunca ser usado, mas certamente moldaria a investigação futura em fatoração.

De forma semelhante, um algoritmo hipotético para o problema de satisfatibilidade booleana com um limite de tempo grande, mas polinomial, tal como

Θ

(

n

2

100

)

{\displaystyle \Theta {\bigl (}n^{2^{100}}{\bigr )}}

, embora inutilizável na prática, resolveria o problema P versus NP, considerado o problema em aberto mais importante da ciência da computação e um dos Problemas do Prémio Millennium.

Exemplos

Multiplicação de inteiros Um exemplo de um algoritmo galáctico é a forma mais rápida conhecida de multiplicar dois números, baseada numa transformada de Fourier de dimensão 1729. O algoritmo necessita de

O ( n log ⁡ n )

{\displaystyle O(n\log n)}

operações de bits, mas como as constantes ocultas pela notação Grande-O são demasiado grandes, ele nunca é usado na prática. No entanto, isto também demonstra por que os algoritmos galácticos ainda podem ser úteis. Os autores afirmam: "estamos esperançosos de que, com refinamentos adicionais, o algoritmo possa tornar-se prático para números com meramente bilhões ou trilhões de dígitos."

Testes de primalidade O teste de primalidade AKS é galáctico. É o mais teoricamente sólido de qualquer algoritmo conhecido que pode receber um número arbitrário e dizer se é um primo. Em particular, é comprovadamente de tempo polinomial, determinístico e incondicionalmente correto. Todos os outros algoritmos conhecidos falham em pelo menos um destes critérios, mas as deficiências são menores e os cálculos são muito mais rápidos, razão pela qual são usados em seu lugar. A ECPP na prática é executada muito mais rapidamente que o AKS, mas nunca se provou que seja de tempo polinomial. O teste de Miller-Rabin também é muito mais rápido que o AKS, mas produz apenas um resultado probabilístico. No entanto, a probabilidade de erro pode ser reduzida a valores arbitrariamente pequenos (digamos

<

10

− 100

{\displaystyle <10^{-100}}

), o que é suficientemente bom para fins práticos. Existe também uma versão determinística do teste de Miller-Rabin, que é executada em tempo polinomial sobre todas as entradas, mas a sua correção depende da hipótese generalizada de Riemann (que é amplamente aceita, mas não provada). A existência destas alternativas (muito) mais rápidas significa que o AKS não é usado na prática.

Multiplicação de matrizes A primeira melhoria em relação à multiplicação de matrizes por força bruta (que requer

O (

n

3

)

{\displaystyle O(n^{3})}

operações) foi o algoritmo de Strassen: um algoritmo recursivo que necessita de

O (

n

2.807

)

{\displaystyle O(n^{2.807})}

operações. Este algoritmo não é galáctico e é usado na prática. Extensões adicionais a este, usando uma teoria dos grupos sofisticada, são o algoritmo de Coppersmith-Winograd e os seus sucessores ligeiramente melhores, necessitando de

O (

n

2.373

)

{\displaystyle O(n^{2.373})}

operações. Estes são galácticos – "Não obstante, sublinhamos que tais melhorias são apenas de interesse teórico, uma vez que as enormes constantes envolvidas na complexidade da multiplicação rápida de matrizes geralmente tornam estes algoritmos impraticáveis."

Capacidade de canal de comunicação Claude Shannon demonstrou um código simples, mas assintoticamente ideal, que consegue atingir a capacidade teórica de um canal de comunicação. O método requer a atribuição de uma palavra de código aleatória a todas as mensagens possíveis de

n

{\displaystyle n}

bits, e a posterior descodificação passa por encontrar a palavra de código mais próxima. Se

n

{\displaystyle n}

for escolhido para ser suficientemente grande, este código supera qualquer outro código existente e pode aproximar-se arbitrariamente da capacidade do canal. Infelizmente, qualquer

n

{\displaystyle n}

suficientemente grande para superar os códigos existentes é também completamente impraticável. Estes códigos, embora nunca tenham sido usados, inspiraram décadas de investigação em algoritmos mais práticos que hoje conseguem atingir taxas arbitrariamente próximas da capacidade do canal.

Subgrafos O problema de decisão sobre se um grafo

G

{\displaystyle G}

contém

H

{\displaystyle H}

como um menor é, em geral, NP-completo, mas onde

H

{\displaystyle H}

é fixo, este pode ser resolvido em tempo polinomial. O tempo de execução para testar se

H

{\displaystyle H}

é um menor de

G

{\displaystyle G}

neste caso é de

O (

n

2

)

{\displaystyle O(n^{2})}

, onde

n

{\displaystyle n}

é o número de vértices em

G

{\displaystyle G}

e a notação Grande-O esconde uma constante que depende superexponencialmente de

H

{\displaystyle H}

. A constante é maior que

2 ↑↑ ( 2 ↑↑ ( 2 ↑↑ ( h

/

2 ) ) )

{\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}

na notação de setas de Knuth, onde

h

{\displaystyle h}

é o número de vértices em

H

{\displaystyle H}

. Mesmo o caso de

h = 4

{\displaystyle h=4}

não pode ser razoavelmente calculado, pois a constante é maior que 2 pentado por 4, ou 2 tetrado por 65536, ou seja,

2 ↑↑↑ 4 =

65536

2 =

2

2

⋅

⋅

2

⏟

65536

{\displaystyle 2\uparrow \uparrow \uparrow 4={}^{65536}2=\underbrace {2^{2^{\cdot ^{\cdot ^{2}}}}} _{65536}}

.

Quebras criptográficas No jargão da criptografia, uma "quebra" (break) é qualquer ataque em expectativa mais rápido do que a força bruta – ou seja, realizar uma tentativa de desencriptação para cada chave possível. Para muitos sistemas criptográficos, já são conhecidas quebras, mas elas continuam a ser praticamente inviáveis com a tecnologia atual. Um exemplo é o melhor ataque conhecido contra o AES de 128 bits, que exige "apenas"

2

126

{\displaystyle 2^{126}}

operações. Apesar de serem impraticáveis, as quebras teóricas podem fornecer compreensões profundas sobre os padrões de vulnerabilidade, o que por vezes conduz à descoberta de quebras que podem efetivamente ser exploradas.

Problema do caixeiro-viajante Durante várias décadas, a melhor aproximação conhecida para o problema do caixeiro-viajante num espaço métrico foi o muito simples algoritmo de Christofides, que produzia um caminho que era no máximo 50% mais longo do que o ótimo global. (Muitos outros algoritmos conseguiam, geralmente, ter um desempenho muito melhor, mas não era possível prová-lo matematicamente.) Em 2020, foi descoberto um algoritmo mais recente e muito mais complexo que consegue superar essa margem em

10

− 34

{\displaystyle 10^{-34}}

por cento. Embora nunca ninguém vá mudar para este algoritmo devido à sua minúscula melhoria no pior caso, ele ainda é considerado importante porque "esta minúscula melhoria rompe um impasse tanto teórico quanto psicológico".

Pesquisa de Hutter Um único algoritmo, a "pesquisa de Hutter" (Hutter search), consegue resolver qualquer problema bem definido num tempo assintoticamente ideal, existindo no entanto algumas ressalvas. Este funciona pesquisando através de todos os algoritmos possíveis (pelo tempo de execução), enquanto simultaneamente pesquisa todas as provas formais possíveis (pelo comprimento da prova), procurando uma prova de correção para cada algoritmo. Dado que a prova de correção tem um tamanho finito, isso "apenas" adiciona um termo constante e não afeta o tempo de execução assintótico. No entanto, esta constante é tão grande que o algoritmo se torna inteiramente impraticável. Por exemplo, se a prova de correção mais curta de um dado algoritmo tiver 1000 bits de comprimento, a pesquisa examinará primeiro, pelo menos,

2

999

{\displaystyle 2^{999}}

outras provas potenciais. A pesquisa de Hutter está intimamente relacionada com a indução de Solomonoff, que é uma formalização da inferência bayesiana. Todas as teorias computáveis (tal como implementadas por programas de computador) que descrevem perfeitamente as observações anteriores são usadas para calcular a probabilidade da observação seguinte, sendo atribuído um peso maior às teorias computáveis mais curtas. Mais uma vez, a pesquisa sobre todas as explicações possíveis torna este procedimento um problema galáctico.

Otimização Está provado que o recozimento simulado (simulated annealing), quando usado com um cronograma de arrefecimento logarítmico, consegue encontrar o ótimo global de qualquer problema de otimização. Contudo, esse cronograma de arrefecimento resulta em tempos de execução que são inteiramente impraticáveis, não sendo por isso utilizado. No entanto, o conhecimento da existência deste algoritmo ideal conduziu a variantes práticas que, hoje, conseguem encontrar soluções muito boas (embora não comprovadamente ótimas) para problemas complexos de otimização.

Árvores de extensão mínima O algoritmo de tempo linear esperado para a MST é capaz de descobrir a árvore de extensão mínima de um grafo em

O ( m + n )

{\displaystyle O(m+n)}

, onde

m

{\displaystyle m}

é o número de arestas e

n

{\displaystyle n}

é o número de nós do grafo. No entanto, o fator constante que é ocultado pela notação Grande-O é enorme o suficiente para tornar o algoritmo impraticável na realidade. Existe uma implementação disponível publicamente e, de acordo com as constantes de implementação estimadas de forma experimental, o algoritmo só seria mais rápido do que o algoritmo de Borůvka para os grafos em que

m + n > 9 ⋅

10

151

{\displaystyle m+n>9\cdot 10^{151}}

.

Tabelas de Hash Investigadores descobriram um algoritmo que alcança o desempenho assintótico comprovadamente melhor possível em termos do compromisso entre o tempo e o espaço (time-space tradeoff). Mas ele permanece como algo puramente teórico: "Apesar da eficiência sem precedentes da nova tabela de hash, é improvável que alguém tente construí-la tão cedo. É simplesmente demasiado complicada de construir." e "na prática, as constantes realmente importam. No mundo real, um fator de 10 significa o fim do jogo."

Conectividade em grafos não direcionados A conectividade em grafos não direcionados (também conhecida como USTCON, de Undirected Source-Target CONnectivity) é o problema de decidir se existe um caminho entre dois nós num grafo não direcionado, ou seja, se eles se encontram na mesma componente conectada. Quando a utilização de um espaço de

O ( N )

{\displaystyle O(N)}

é permitida, são conhecidas e usadas há décadas soluções em tempo polinomial, tais como o algoritmo de Dijkstra. Mas durante muitos anos desconhecia-se se isso poderia ser feito deterministicamente num espaço de

O ( log ⁡ N )

{\displaystyle O(\log N)}

(classe L), muito embora já se soubesse que era possível com algoritmos aleatorizados (classe RL). Um artigo revolucionário publicado em 2008 por Omer Reingold demonstrou que a USTCON pertence, de facto, à classe L, fornecendo assim um algoritmo com uma exigência de espaço assintoticamente muito melhor. No entanto, a constante extremamente grande do algoritmo que fica oculta pela notação

O ( log ⁡ N )

{\displaystyle O(\log N)}

faz com que, em qualquer problema realista, o método consuma significativamente mais memória e mais tempo de computação do que os algoritmos de

O ( N )

{\displaystyle O(N)}

bem conhecidos. Apesar de não ser usado na prática, o artigo continua a ser um enorme marco na teoria da complexidade, tendo já sido citado mais de 1000 vezes até ao ano de 2026.

Códigos de verificação de paridade de baixa densidade Os códigos de verificação de paridade de baixa densidade, também conhecidos por códigos LDPC ou códigos de Gallager, são um bom exemplo de um algoritmo que era totalmente galáctico aquando da sua concepção inicial, mas que se tornou prático à medida que os sistemas de computação evoluíram. Foram originalmente concebidos por Robert G. Gallager na sua dissertação de doutoramento no Instituto de Tecnologia de Massachusetts (MIT) em 1960. Embora o seu desempenho na altura fosse muito superior ao de outros códigos dessa época — conseguindo inclusive alcançar o limite de Gilbert-Varshamov para códigos lineares —, os códigos foram amplamente ignorados pela comunidade científica, uma vez que o seu algoritmo iterativo de descodificação possuía um custo computacional proibitivamente alto para o hardware disponível na época. O interesse renovado nos códigos LDPC só emergiu no seguimento da invenção dos muito aparentados turbo códigos (em 1993), cujo algoritmo iterativo de descodificação superou de forma análoga outros códigos em utilização. Os códigos LDPC foram então redescobertos em 1996 e começaram a ficar muito populares por serem uma alternativa isenta de patentes. Mesmo estando as patentes dos turbo códigos agora expiradas, os códigos LDPC também dispõem de fortes vantagens técnicas inerentes e são atualmente usados em muitas aplicações ao redor do mundo.

Triangulação de polígonos A triangulação de polígonos consiste na divisão de um determinado polígono num conjunto de triângulos que não se sobrepõem. O matemático Bernard Chazelle demonstrou em 1991 que qualquer polígono simples pode ser perfeitamente triangulado em tempo linear. No entanto, o algoritmo que ele propôs para esse efeito é extremamente complexo, e algoritmos muito mais simples com um desempenho quase-linear de

O ( N

log

∗

⁡ N )

{\displaystyle O(N\log ^{*}N)}

encontram-se prontamente disponíveis, pelo que esses acabam por ser usados como alternativa. "O seu [de Chazelle] trabalho representa um importante avanço teórico. No entanto, o seu algoritmo de

O ( n )

{\displaystyle O(n)}

revelou-se muito difícil de programar e, assim, do conhecimento dos autores, ainda não existe nenhuma implementação prática disponível."

Ver também P versus NP Código turbo

Referências