Algoritmo galáctico
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.
Mesmo que nunca sejam usados na prática, os algoritmos galácticos ainda podem contribuir para a ciência da computação: 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.
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". 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.
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.
