Um algoritmo galáctico é um algoritmo com desempenho teórico (assintótico) recorde, mas que não é utilizado na prática devido a restrições reais de execução. As razões típicas são o fato de os ganhos de desempenho só se manifestarem em problemas de dimensões tão vastas que nunca ocorrem na prática, ou porque a complexidade intrínseca do algoritmo supera qualquer ganho marginal de desempenho no mundo real. Os algoritmos galácticos foram assim denominados por Richard Lipton e Ken Regan, porque eles jamais serão executados sobre conjuntos de dados existentes na Terra.
Possíveis casos de uso Mesmo que nunca sejam aplicados na prática, os algoritmos galácticos podem contribuir significativamente para a ciência da computação: Um algoritmo, ainda que impraticável, pode introduzir novas técnicas conceituais que eventualmente venham a ser utilizadas na concepção de algoritmos práticos (consulte, por exemplo, a seção sobre capacidade do canal de comunicação, abaixo). O poder computacional disponível pode evoluir até atingir o ponto de equilíbrio (crossover point), de tal modo que um algoritmo anteriormente inviável se torne viável (consulte, por exemplo, a seção sobre códigos de verificação de paridade de baixa densidade, abaixo). Um algoritmo impraticável pode demonstrar que limites conjeturados são teoricamente atingíveis, ou que limites propostos estão incorretos, fazendo avançar a teoria da complexidade e dos algoritmos (ver, por exemplo, o algoritmo de Reingold para conectividade em grafos não direcionados). Como afirma Lipton: De forma análoga, um algoritmo hipotético para o problema de satisfatibilidade booleana com um limitante temporal grande, porém polinomial, tal como , muito embora inútil na prática, resolveria o problema P versus NP, considerado o problema aberto mais fundamental da ciência da computação e um dos Problemas do Prêmio Millennium.
Exemplos Multiplicação de inteiros Um exemplo proeminente de algoritmo galáctico é o método mais rápido conhecido para multiplicar dois números, baseado em uma transformada de Fourier de 1729 dimensões. Ele requer operações de bits, mas, como as constantes ocultas pela notação Big O são astronômicas, ele jamais é empregado na prática. Não obstante, o método também exemplifica como algoritmos galácticos conservam utilidade prospectiva: os autores afirmam que "temos a esperança de que, com refinamentos adicionais, o algoritmo possa tornar-se prático para números com meros bilhões ou trilhões de dígitos."
Testes de primalidade O teste de primalidade AKS é galáctico. Trata-se do algoritmo com fundamentação teórica mais robusta conhecido para receber um número arbitrário e determinar se ele é primo. Em particular, é comprovadamente de tempo polinomial, determinístico e incondicionalmente correto. Todos os demais algoritmos conhecidos falham em pelo menos um desses três critérios; contudo, suas deficiências são contornáveis e suas computações são ordens de magnitude mais velozes, sendo por isso utilizados na prática. O ECPP executa em termos práticos muito mais rápido do que o AKS, mas jamais foi provado como sendo de tempo estritamente polinomial. O teste de primalidade de Miller-Rabin também é muito mais veloz que o AKS, mas produz um resultado probabilístico — embora a probabilidade de erro possa ser reduzida para valores arbitrariamente diminutos (digamos, ), o que é plenamente aceitável para aplicações práticas. Existe ainda uma variante determinística do teste de Miller-Rabin que roda em tempo polinomial sobre todas as entradas, mas cuja correção depende da validade da hipótese generalizada de Riemann (amplamente aceita, porém não demonstrada formalmente). A existência dessas alternativas substancialmente mais rápidas inviabiliza a aplicação do AKS em cenários reais.
Multiplicação de matrizes O primeiro avanço sobre a multiplicação ingênua de matrizes por força bruta (que demanda operações) foi o algoritmo de Strassen: um algoritmo recursivo que consome operações. Esse método não é galáctico e encontra uso prático real. Extensões posteriores fundamentadas em técnicas sofisticadas da teoria dos grupos deram origem ao algoritmo de Coppersmith-Winograd e aos seus sucessores levemente otimizados, atingindo operações. Estes últimos são estritamente galácticos: "Ressaltamos, não obstante, que tais melhorias são de interesse puramente teórico, visto que as enormes constantes envolvidas na complexidade da multiplicação rápida de matrizes usualmente tornam esses algoritmos impraticáveis."
Capacidade do canal de comunicação Claude Shannon demonstrou a existência de um código simples, porém assintoticamente ótimo, capaz de atingir a capacidade teórica de um canal de comunicação. O método baseia-se na atribuição de uma palavra-código aleatória a cada mensagem de bits possível, decodificando-a pela identificação da palavra-código mais próxima. Se for escolhido suficientemente grande, o método supera qualquer código concreto existente e aproxima-se arbitrariamente do limite de Shannon do canal. Infelizmente, qualquer valor de grande o bastante para superar os códigos práticos é inteiramente inviável de implementar. Tais códigos, muito embora jamais utilizados em sua forma original, inspiraram décadas de investigação científica em esquemas mais tratáveis que hoje conseguem atingir taxas arbitrariamente próximas à capacidade do canal.
Subgrafos O problema de decisão de determinar se um grafo contém um grafo como menor é NP-completo em geral; contudo, quando é fixado a priori, o problema pode ser resolvido em tempo polinomial. O tempo de execução para verificar se é um menor de neste caso é de , onde é o número de vértices de e a notação Big O omite uma constante que depende superexponencialmente de . A constante oculta é superior a na notação de Knuth, onde é a quantidade de vértices de . Mesmo para o caso elementar de , a computação é fisicamente inviável, já que a constante é superior a 2 pentado por 4, ou 2 tetrado por 65536, isto é:
Quebras criptográficas No jargão da criptografia, uma "quebra" designa qualquer ataque cujo tempo esperado seja estritamente inferior ao da força bruta — isto é, testar sistematicamente cada chave possível até encontrar a correta. Para inúmeros sistemas criptográficos, conhecem-se quebras teóricas que continuam, todavia, inteiramente inviáveis perante a tecnologia atual. Um exemplo é o ataque teórico mais eficiente conhecido contra o AES de 128 bits, que requer operações. Apesar de impraticáveis na execução direta, quebras teóricas oferecem percepções profundas sobre padrões de vulnerabilidade estruturais, por vezes pavimentando o caminho para a descoberta de ataques exploráveis.
Problema do caixeiro-viajante Durante décadas, a melhor aproximação conhecida para o problema do caixeiro-viajante métrico foi o simples algoritmo de Christofides, que garantia um percurso no máximo 50% mais longo que a solução ótima (muitos outros algoritmos costumavam ter desempenho sensivelmente melhor na prática, mas careciam de garantias matemáticas rigorosas para o pior caso). Em 2020, foi descoberto um algoritmo novo e consideravelmente mais complexo capaz de superar essa margem por por cento. Embora nenhum sistema prático venha a adotar esse algoritmo em razão de um ganho tão ínfimo no pior caso, ele é considerado um marco na teoria porque "essa melhoria minúscula rompe um impasse tanto teórico quanto psicológico".
Busca de Hutter Um algoritmo singular, a "Busca de Hutter", é capaz de solucionar qualquer problema formalmente bem definido em tempo assintoticamente ótimo, ressalvadas certas particularidades teóricas. Seu princípio consiste em efetuar uma busca exaustiva sobre todos os algoritmos possíveis (ordenados por seu tempo de execução), enquanto simultaneamente busca entre todas as demonstrações formais possíveis (ordenadas pelo comprimento do texto da prova), à procura de uma prova de correção formal para cada algoritmo. Como a prova de correção possui tamanho finito, ela adiciona "apenas" um fator constante que não afeta a taxa assintótica de crescimento. Essa constante, contudo, é tão extraordinariamente colossal que o algoritmo é inteiramente inviável. Por exemplo, se a demonstração de correção mais curta para determinado algoritmo tiver 1000 bits de comprimento, a busca avaliará pelo menos outras demonstrações potenciais antes de localizá-la.
A busca de Hutter relaciona-se intrinsecamente com a indução de Solomonoff, formalização matemática da inferência bayesiana. Todas as teorias computáveis (modeladas por programas) que descrevem com exatidão as observações passadas são mobilizadas para calcular a probabilidade da observação subsequente, atribuindo-se peso preponderante às teorias computáveis mais curtas. Mais uma vez, o espaço exaustivo de hipóteses torna o procedimento galáctico.
Otimização O algoritmo de recozimento simulado (simulated annealing), quando executado sob um cronograma de resfriamento logarítmico, provou convergir assintoticamente para o ótimo global de qualquer problema de otimização. Todavia, tal regime de resfriamento resulta em tempos de execução fisicamente impraticáveis, não sendo utilizado em problemas reais. Contudo, a comprovação formal da existência desse método ideal estimulou a elaboração de variantes heurísticas eficientes capazes de encontrar soluções de alta qualidade (ainda que sem garantia de otimalidade estrita) para problemas de grande complexidade.
Árvores geradoras mínimas O algoritmo de árvore geradora mínima em tempo linear esperado identifica a árvore geradora mínima de um grafo com complexidade temporal , onde denota a quantidade de arestas e o total de vértices do grafo. Todavia, o fator constante embutido na notação Big O é monumental a ponto de inviabilizar o algoritmo para instâncias práticas. Uma implementação encontra-se disponível publicamente; perante as constantes estimadas experimentalmente no código, o método só superaria o desempenho do clássico algoritmo de Borůvka em grafos nos quais .
Tabelas de dispersão (hash) Pesquisadores desenvolveram um algoritmo que atinge o compromisso tempo-espaço assintótico comprovadamente ótimo para tabelas de dispersão dinâmicas sucintas. Trata-se, contudo, de uma estrutura estritamente teórica: "Apesar da eficiência sem precedentes da nova tabela de dispersão, é improvável que alguém tente construí-la tão cedo. Ela é simplesmente complexa demais para ser implementada", além do fato de que "na prática, as constantes importam criticamente. No mundo real, um fator de 10 inviabiliza o projeto".
Conectividade em grafos não direcionados A conectividade em grafos não direcionados (conhecida pela sigla USTCON, de Undirected Source-Target CONnectivity) é o problema de determinar se existe um caminho conectando dois vértices em um grafo não direcionado ou, equivalentemente, se ambos integram a mesma componente conexa. Quando se dispõe de espaço de memória , soluções polinomiais clássicas como a busca em largura ou o algoritmo de Dijkstra são amplamente empregadas há décadas. Durante muito tempo, no entanto, permaneceu em aberto se o problema admitia resolução determinística em espaço logarítmico (a classe de complexidade L), muito embora já se soubesse que pertencia à classe probabilística correspondente (RL).
Em 2008, um artigo revolucionário de Omer Reingold provou formalmente que o problema USTCON pertence de fato à classe L,. fornecendo um algoritmo com exigência de espaço assintoticamente superior. Contudo, a constante oculta pelo limitante no algoritmo de Reingold é tão gigantesca que, para qualquer instância realista, ele consome significativamente mais tempo e memória do que as abordagens convencionais . Apesar de impraticável, a descoberta marcou época na teoria da computação, acumulando mais de um milhar de citações acadêmicas.
Códigos de verificação de paridade de baixa densidade