Algoritmo galáctico - Galactic algorithm

Um algoritmo galáctico é aquele que supera qualquer outro algoritmo para problemas que são suficientemente grandes, mas onde "suficientemente grande" é tão grande que o algoritmo nunca é usado na prática. Os algoritmos galácticos foram assim chamados por Richard Lipton e Ken Regan, pois nunca serão usados em nenhum dos conjuntos de dados meramente terrestres que encontramos aqui na Terra.

Casos de uso

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 se impraticável, pode mostrar novas técnicas que podem eventualmente ser usadas para criar algoritmos práticos.
Os tamanhos dos computadores podem alcançar o ponto de cruzamento, de modo que um algoritmo antes impraticável se torna prático.
Um algoritmo impraticável ainda pode demonstrar que limites conjecturados podem ser alcançados, ou que os limites propostos estão errados e, portanto, avançar a teoria dos algoritmos. Como afirma Lipton:
Isso por si só pode ser importante e muitas vezes é um grande motivo para encontrar esses algoritmos. Por exemplo, se amanhã houvesse uma descoberta que mostrasse que existe um algoritmo de fatoração com um limite de tempo enorme, mas provavelmente polinomial, isso mudaria nossas crenças sobre a fatoração. O algoritmo pode nunca ser usado, mas certamente moldaria a pesquisa futura em fatoração.
Da mesma forma, um algoritmo para o problema de satisfatibilidade booleana , embora inutilizável na prática, resolveria o problema P versus NP , o problema aberto mais importante em ciência da computação e um dos Problemas do Prêmio do Milênio . ${\ displaystyle O {\ bigl (} n ^ {2 ^ {100}} {\ bigr)}}$

Exemplos

Multiplicação inteira

Um exemplo de algoritmo galáctico é a maneira mais rápida conhecida de multiplicar dois números , que se baseia em uma transformada de Fourier de 1729 dimensões . Isso significa que ele não atingirá sua eficiência declarada até que os números tenham pelo menos 2 ^{1729 ¹²} bits (pelo menos 10 ^{10 ³⁸} dígitos), que é muito maior do que o número de átomos no universo conhecido. Portanto, esse algoritmo nunca é usado na prática.

Multiplicação da matriz

A primeira melhoria sobre a multiplicação por força bruta é o algoritmo Strassen , um algoritmo recursivo que é . Este algoritmo não é galáctico e é usado na prática. Outras extensões disso, usando a sofisticada teoria de grupo, são o algoritmo Coppersmith – Winograd e seus sucessores ligeiramente melhores . Estes são galácticos - "No entanto, enfatizamos 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 esses algoritmos impraticáveis." ${\ displaystyle O (n ^ {3})}$ ${\ displaystyle O (n ^ {2.807})}$ ${\ displaystyle O (n ^ {2.373})}$

Capacidade do canal de comunicação

Claude Shannon mostrou um código simples, mas pouco prático , que poderia atingir a capacidade de um canal de comunicação . Requer a atribuição de uma palavra-código aleatória a cada mensagem de bits possível e , em seguida, a decodificação localizando a palavra-código mais próxima. Se for escolhido grande o suficiente, supera qualquer código existente e pode ficar arbitrariamente próximo da capacidade do canal. Infelizmente, qualquer grande o suficiente para superar os códigos existentes também é completamente impraticável. Esses códigos, embora nunca usados, inspiraram décadas de pesquisa em algoritmos mais práticos que hoje podem atingir taxas arbitrariamente próximas à capacidade do canal. ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle n}$

Subgráficos

O problema de decidir se um gráfico contém como menor é NP-completo em geral, mas onde é fixo, pode ser resolvido em tempo polinomial. O tempo de execução para testar se é menor neste caso é , onde está o número de vértices em e a notação O grande esconde uma constante que depende superexponencialmente de . A constante é maior que (usando a notação de seta para cima de Knuth ), onde é o número de vértices em . Mesmo para números pequenos, como a constante resulta em , um número com 19729 dígitos decimais. Pois , não pode ser computado razoavelmente: onde a parte é uma torre de potência de 16 cópias de 2, um número tão grande que seu valor exato não pode ser calculado de forma prática. Toda a expressão é uma torre de poder de tantas cópias de 2. ${\ displaystyle G}$ ${\ displaystyle H}$ ${\ displaystyle H}$ ${\ displaystyle H}$ ${\ displaystyle G}$ ${\ displaystyle O (n ^ {2})}$ ${\ displaystyle n}$ ${\ displaystyle G}$ ${\ displaystyle H}$ ${\ displaystyle 2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (h / 2)))}$ ${\ displaystyle h}$ ${\ displaystyle H}$ ${\ displaystyle h = 4}$ ${\ displaystyle 2 ^ {65536}}$ ${\ displaystyle h = 6}$ ${\ displaystyle 2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (6/2))) = 2 \ uparrow \ uparrow {\ Bigl (} 2 ^ {\ cdot ^ {\ cdot ^ {2 }}} {\ Bigr)}}$ ${\ displaystyle 2 ^ {\ cdot ^ {\ cdot ^ {2}}}}$

Quebras criptográficas

Para os criptógrafos, uma "quebra" criptográfica é qualquer coisa mais rápida do que um ataque de força bruta - ou seja, realizar uma descriptografia de teste para cada chave possível. Em muitos casos, embora sejam os métodos mais conhecidos, ainda são inviáveis com a tecnologia atual. Um exemplo é o melhor ataque conhecido contra AES de 128 bits , que leva apenas operações. Apesar de serem impraticáveis, as interrupções teóricas às vezes podem fornecer uma visão sobre os padrões de vulnerabilidade. ${\ displaystyle 2 ^ {126}}$

Problema do caixeiro viajante

Por várias décadas, a aproximação mais conhecida para o problema do caixeiro viajante em um espaço métrico foi o algoritmo muito simples de Christofides, que produziu um caminho no máximo 50% mais longo do que o ótimo. (Muitos outros algoritmos normalmente poderiam ter um desempenho muito melhor, mas não podiam ser comprovados.) Em 2020, um algoritmo mais novo e muito mais complexo foi descoberto que pode superar isso em porcentagem. Embora ninguém nunca mude para esse algoritmo para sua pequena melhoria de pior caso, ele ainda é considerado importante porque "essa melhoria minúscula rompe um impasse teórico e um psicológico". ${\ displaystyle 10 ^ {- 34}}$

Pesquisa Hutter

Existe um único algoritmo conhecido como "busca Hutter" que pode resolver qualquer problema bem definido em um tempo assintoticamente ideal, exceto algumas ressalvas. No entanto, suas constantes ocultas no tempo de execução são tão grandes que nunca seria prático para nada.

Languages

In other projects