Galaktik algoritma - Galactic algorithm

Bir galaktik algoritma , yeterince büyük, ancak "yeterince büyük"ün o kadar büyük olduğu ve algoritmanın pratikte hiçbir zaman kullanılmadığı problemler için diğer herhangi bir algoritmadan daha iyi performans gösteren bir algoritmadır. Galaktik algoritmalar, Richard Lipton ve Ken Regan tarafından, burada, Dünya'da bulduğumuz yalnızca karasal veri kümelerinin hiçbirinde asla kullanılmayacakları için böyle adlandırıldı .

Kullanım durumları

Pratikte hiç kullanılmasalar bile, galaktik algoritmalar yine de bilgisayar bilimine katkıda bulunabilir:

Bir algoritma, pratik olmasa bile, sonunda pratik algoritmalar oluşturmak için kullanılabilecek yeni teknikleri gösterebilir.
Bilgisayar boyutları geçiş noktasına yetişebilir, böylece daha önce pratik olmayan bir algoritma pratik hale gelir.
Pratik olmayan bir algoritma, tahmin edilen sınırların elde edilebileceğini veya önerilen sınırların yanlış olduğunu hala gösterebilir ve dolayısıyla algoritma teorisini ilerletebilir. Lipton'un belirttiği gibi:
Bu tek başına önemli olabilir ve genellikle bu tür algoritmaları bulmak için harika bir nedendir. Örneğin, yarın çok büyük ama kanıtlanabilir bir polinom zaman sınırına sahip bir faktoring algoritması olduğunu gösteren bir keşif olsaydı, bu bizim faktoring hakkındaki inançlarımızı değiştirirdi. Algoritma asla kullanılmayabilir, ancak gelecekteki araştırmaları kesinlikle faktoringe yönlendirecektir.
Benzer şekilde, Boolean tatmin edilebilirlik problemi için bir algoritma pratikte kullanılamasa da, bilgisayar bilimlerindeki en önemli açık problem ve Milenyum Ödül Problemlerinden biri olan P'ye karşı NP problemini çözecektir . $O{\bigl (}n^{2^{100}}{\bigr )}$

Örnekler

tamsayı çarpma

Bir galaktik algoritma örneği, 1729 boyutlu Fourier dönüşümüne dayanan iki sayıyı çarpmanın bilinen en hızlı yoludur . Bu, sayıların bilinen evrendeki atom sayısından çok daha büyük olan en az 2 ¹⁷²⁹^¹² bit (en az 10 ¹⁰^³⁸ basamak) olana kadar belirtilen verimliliğine ulaşmayacağı anlamına gelir . Yani bu algoritma pratikte asla kullanılmaz.

matris çarpımı

Kaba güç çarpma üzerine ilk iyileştirme, bir Strassen algoritması , bir dönüşümlü algoritma . Bu algoritma galaktik değildir ve pratikte kullanılır. Bunun gelişmiş grup teorisini kullanan diğer uzantıları, Coppersmith-Winograd algoritması ve onun biraz daha iyi halefleri olan . Bunlar galaktiktir - "Yine de, hızlı matris çarpımının karmaşıklığında yer alan devasa sabitler genellikle bu algoritmaları kullanışsız hale getirdiğinden, bu tür gelişmelerin yalnızca teorik ilgi olduğunu vurguluyoruz." ${\görüntüleme stili O(n^{3})}$ ${\ Displaystyle O(n^{2.807})}$ ${\ Displaystyle O(n^{2.373})}$

İletişim kanalı kapasitesi

Claude Shannon , bir iletişim kanalının kapasitesine ulaşabilecek basit ama pratik olmayan bir kod gösterdi . Her olası -bit mesajına rastgele bir kod sözcüğü atamayı ve ardından en yakın kod sözcüğünü bularak kodu çözmeyi gerektirir. Eğer büyük yeterince seçilir, bu varolan herhangi bir kod yener ve keyfi olarak yakın kanalın kapasitesi alabilirsiniz. Ne yazık ki, mevcut kodları yenecek kadar büyük herhangi bir şey de tamamen pratik değildir. Bu kodlar, hiç kullanılmamış olsalar da, günümüzde kanal kapasitesine keyfi olarak yakın oranlar elde edebilen daha pratik algoritmalara yönelik onlarca yıllık araştırmaya ilham verdi. ${\görüntüleme stili n}$ ${\görüntüleme stili n}$ ${\görüntüleme stili n}$

alt grafikler

Bir grafiğin minör olarak içerip içermediğine karar verme sorunu genel olarak NP-tamamlıdır , ancak nerede sabitlenirse polinom zamanında çözülebilir. Bu durumda minör olup olmadığını test etmek için çalışma süresi , köşelerin sayısı nerede ve büyük O notasyonu , üstel olarak bağlı olan bir sabiti gizler . Sabit daha büyüktür (kullanarak Knuth yukarı ok gösterimde burada,) içinde köşe sayısıdır . gibi küçük sayılar için bile , sabit sonuç olarak 19729 ondalık basamaklı bir sayıdır. için , makul bir şekilde hesaplanamaz: , parça 2'nin 16 kopyasından oluşan bir güç kulesi olduğunda, o kadar büyük bir sayı tam değeri pratik olarak hesaplanamaz. Tüm ifade, 2'nin bu kadar çok kopyasının bir güç kulesidir. ${\görüntüleme stili G}$ ${\görüntüleme stili H}$ ${\görüntüleme stili H}$ ${\görüntüleme stili H}$ ${\görüntüleme stili G}$ ${\ Displaystyle O(n^{2})}$ ${\görüntüleme stili n}$ ${\görüntüleme stili G}$ ${\görüntüleme stili H}$ $2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))$ ${\görüntüleme stili h}$ ${\görüntüleme stili H}$ ${\görüntüleme stili h=4}$ ${\ Displaystyle 2^{65536}}$ ${\görüntüleme stili h=6}$ $2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (6/2)))=2\uparrow \uparrow {\Bigl (}2^{\cdot ^{\cdot ^{2 }}}{\Büyük )}$ $2^{\cdot ^{\cdot ^{2}}}$

kriptografik kırılmalar

Kriptograflar için kriptografik bir "kırılma", bir kaba kuvvet saldırısından daha hızlı olan herhangi bir şeydir - yani, olası her anahtar için bir deneme şifre çözme gerçekleştirme. Çoğu durumda, en iyi bilinen yöntemler olmalarına rağmen, mevcut teknoloji ile hala mümkün değildir. Bir örnek, yalnızca işlem alan 128 bit AES'ye karşı bilinen en iyi saldırıdır . Pratik olmamasına rağmen, teorik molalar bazen güvenlik açığı kalıplarına ilişkin fikir verebilir. ${\ Displaystyle 2^{126}}$

Gezgin satıcı sorunu

Birkaç on yıl boyunca, bir metrik uzayda gezgin satıcı problemine en iyi bilinen yaklaşım , optimumdan en fazla %50 daha uzun bir yol üreten çok basit Christofides algoritmasıydı . (Diğer birçok algoritma genellikle çok daha iyisini yapabilirdi, ancak bunu kanıtlayamadı.) 2020'de, bunu yüzde olarak geçebilecek daha yeni ve çok daha karmaşık bir algoritma keşfedildi . Hiç kimse bu algoritmaya çok hafif en kötü durum iyileştirmesi için geçmeyecek olsa da, "bu küçük gelişme hem teorik hem de psikolojik bir engeli aştığı için" hala önemli kabul ediliyor. ${\görüntüleme stili 10^{-34}}$

Hutter arama

"Hutter arama" olarak bilinen, iyi tanımlanmış herhangi bir sorunu asimptotik olarak en uygun zamanda çözebilen ve bazı uyarıları engelleyen tek bir algoritma vardır. Ancak, çalışma süresindeki gizli sabitleri o kadar büyüktür ki, hiçbir şey için asla pratik olmaz.

Languages

In other projects