Algorytm galaktyczny

Algorytm galaktyczny to taki, który przewyższa każdy inny algorytm w przypadku problemów, które są wystarczająco duże, ale gdzie „wystarczająco duży” jest tak duży, że algorytm nigdy nie jest używany w praktyce. Algorytmy galaktyczne zostały tak nazwane przez Richarda Liptona i Kena Regana, ponieważ nigdy nie będą używane w żadnych zbiorach danych na Ziemi.

Możliwe przypadki użycia

Algorytmy galaktyczne, nawet jeśli nigdy nie zostaną użyte w praktyce, nadal mogą przyczynić się do rozwoju informatyki:

Algorytm, nawet jeśli jest niepraktyczny, może pokazać nowe techniki, które mogą ostatecznie zostać wykorzystane do stworzenia praktycznych algorytmów.
Dostępna moc obliczeniowa może dogonić punkt przecięcia, tak że wcześniej niepraktyczny algorytm staje się praktyczny.
Niepraktyczny algorytm może nadal wykazać, że domniemane granice można osiągnąć lub że proponowane granice są błędne, a tym samym rozwija teorię algorytmów. Jak stwierdza Lipton:
Samo to może być ważne i często jest świetnym powodem do znalezienia takich algorytmów. Na przykład, gdyby jutro miało miejsce odkrycie, które pokazałoby, że istnieje algorytm faktoryzacji z ogromnym, ale możliwym do udowodnienia wielomianem w czasie, zmieniłoby to nasze przekonania na temat faktoryzacji. Algorytm może nigdy nie zostać użyty, ale z pewnością ukształtuje przyszłe badania nad faktoringiem.
$problemu$ hipotetyczny duży, ale wielomianowy spełnialności Boole'a , chociaż bezużyteczny w praktyce rozwiązać problem P kontra NP , uważany za najważniejszy otwarty problem w informatyce i jeden z problemów Nagrody Milenijnej .

Przykłady

Mnożenie liczb całkowitych

Przykładem algorytmu galaktycznego jest najszybszy znany sposób mnożenia dwóch liczb , oparty na 1729-wymiarowej transformacie Fouriera . Wymaga $nie$ stałe ukryte w dużej notacji O są używane w Pokazuje jednak również, dlaczego algorytmy galaktyczne mogą być nadal przydatne. Autorzy stwierdzają: „mamy nadzieję, że przy dalszych udoskonaleniach algorytm może stać się praktyczny w przypadku liczb zawierających zaledwie miliardy lub biliony cyfr”.

Mnożenie macierzy

Pierwszym ulepszeniem w stosunku do mnożenia macierzy metodą brute-force (które wymaga ${\ Displaystyle O$ ) był algorytm Strassena : algorytm rekurencyjny, który wymaga $^ {3}$ mnożenia. Ten algorytm nie jest galaktyczny i jest stosowany w praktyce. $algorytm$ rozszerzeniami tego, wykorzystującymi wyrafinowaną teorię grup, są Winograda i jego nieco lepsi następcy, . Są to galaktyczne – „Jednak podkreślamy, że takie ulepszenia mają jedynie znaczenie teoretyczne, ponieważ ogromne stałe związane ze złożonością szybkiego mnożenia macierzy zwykle sprawiają, że te algorytmy są niepraktyczne”.

Przepustowość kanału komunikacyjnego

Claude Shannon pokazał prosty, ale niepraktyczny kod , który mógłby osiągnąć pojemność kanału komunikacyjnego . Wymaga przypisania losowego słowa kodowego do każdej możliwej $-bitowej$ , a następnie dekodowania przez znalezienie najbliższego słowa kodowego. Jeśli $duży$ , pobije to każdy istniejący kod i może dowolnie zbliżyć się do pojemności kanału. Niestety, każdy $,$ jest również całkowicie niepraktyczny. Kody te, choć nigdy nie były używane, zainspirowały dziesięciolecia badań nad bardziej praktycznymi algorytmami, które dziś mogą osiągać szybkości zbliżone do przepustowości kanału.

Wykresy podrzędne

Problem z podjęciem decyzji $,$ czy wykres zawiera jako $drugorzędny$ $,$ jest ogólnie NP-zupełny , ale rozwiązać w czasie wielomianowym. Czas działania do sprawdzenia, czy $}$ $}$ $G$ $w$ tym przypadku to gdzie ${$ to liczba wierzchołków w $a$ notacja dużego O ukrywa stałą, która zależy superwykładniczo od ${\ displaystyle H}$ . Stała jest większa niż ${\ Displaystyle 2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (h / 2))) }$ w notacji Knutha ze strzałką w górę ${\ displaystyle H$ gdzie jest liczbą wierzchołków w $}$ . $h = 4}$ displaystyle nie może być rozsądnie obliczony, ponieważ stała jest większa niż ${\ Displaystyle {\ \ na szczycie {\}} {{\ underbrace {2 ^ { 2^{\cdot ^{\cdot ^{2}}}}} } \na szczycie n}}$ z n = 65536.

Przerwy kryptograficzne

Dla kryptografów „złamanie” kryptograficzne jest czymkolwiek szybszym niż atak brute-force – tj. przeprowadzenie jednego próbnego odszyfrowania dla każdego możliwego klucza. W wielu przypadkach, mimo że są to najbardziej znane metody, nadal są niewykonalne przy obecnej technologii. $operacji$ przykładów jest najlepszy znany atak przeciwko 128-bitowemu , który wymaga tylko . Pomimo tego, że jest to niepraktyczne, teoretyczne przerwy mogą czasami zapewnić wgląd we wzorce podatności na zagrożenia.

Problem komiwojażera

Przez kilka dziesięcioleci najbardziej znanym przybliżeniem problemu komiwojażera w przestrzeni metrycznej był bardzo prosty algorytm Christofidesa , który generował ścieżkę co najwyżej o 50% dłuższą niż optymalna. (Wiele innych algorytmów mogłoby zwykle działać znacznie lepiej, ale nie można $tego udowodnić). W 2020 roku odkryto$ złożony algorytm, który może to przebić o . Chociaż nikt nigdy nie przestawi się na ten algorytm ze względu na jego bardzo nieznaczną poprawę w najgorszym przypadku, nadal uważa się go za ważny, ponieważ „ta niewielka poprawa przełamuje zarówno teoretyczny, jak i psychologiczny zastój”.

Szukaj Huttera

Pojedynczy algorytm, „wyszukiwanie Huttera”, może rozwiązać każdy dobrze zdefiniowany problem w asymptotycznie optymalnym czasie, z wyjątkiem pewnych zastrzeżeń. Działa poprzez przeszukiwanie wszystkich możliwych algorytmów (według czasu wykonywania), jednocześnie przeszukując wszystkie możliwe dowody (według długości dowodu), szukając dowodu poprawności dla każdego algorytmu. Ponieważ dowód poprawności ma skończoną wielkość, dodaje „tylko” stałą i nie wpływa na asymptotyczny czas działania. Jednak ta stała jest tak duża, że algorytm jest całkowicie niepraktyczny. Na przykład, jeśli najkrótszy dowód poprawności danego algorytmu ma długość 1000 bitów, wyszukiwanie najpierw zbada co najmniej 2 ⁹⁹⁹ innych potencjalnych dowodów.

Optymalizacja

że symulowane wyżarzanie , stosowane z logarytmicznym harmonogramem chłodzenia, znajduje globalne optimum każdego problemu optymalizacyjnego. Jednak taki harmonogram chłodzenia skutkuje całkowicie niepraktycznymi czasami pracy i nigdy nie jest używany. Jednak wiedza o istnieniu tego idealnego algorytmu doprowadziła do powstania praktycznych wariantów, które są w stanie znaleźć bardzo dobre (choć nie do udowodnienia optymalne) rozwiązania złożonych problemów optymalizacyjnych.

Minimalne drzewa rozpinające

Oczekiwany $w$ MST w czasie liniowym $m$ $} \displaystyle n}$ minimalne drzewo rozpinające wykresu w , gdzie jest liczbą krawędzi i to liczba węzłów grafu. Jednak stały czynnik, który jest ukryty w notacji Big O, jest wystarczająco duży, aby uczynić algorytm niepraktycznym. Implementacja jest publicznie dostępna i biorąc pod uwagę eksperymentalnie oszacowane stałe implementacji, byłaby szybsza tylko od algorytmu Borůvki dla wykresów, w których ${\ Displaystyle m + n> 9 \ cdot 10 ^ {151}}$ .