Potężne algorytmy zbyt skomplikowane do wdrożenia

Jakie są algorytmy legalnej użyteczności, które są po prostu zbyt skomplikowane, aby je zaimplementować?

Wyjaśnię: nie szukam algorytmów takich jak obecny asymptotyczny algorytm optymalnego mnożenia macierzy (Coppersmith-Winograd), który jest rozsądny do wdrożenia, ale ma stałą, która czyni go bezużytecznym w praktyce. Szukam algorytmów, które mogłyby mieć praktyczną wartość, ale są tak trudne do zakodowania, że ​​nigdy nie zostały zaimplementowane, tylko zaimplementowane w wyjątkowo sztucznych ustawieniach lub tylko zaimplementowane w aplikacjach o wyjątkowym przeznaczeniu.

Również mile widziane są prawie niemożliwe do wdrożenia algorytmy, które mają dobrą asymptotę, ale prawdopodobnie będą miały słabą rzeczywistą wydajność.

Chazelle podał liniowy algorytm czasowy do triangulacji prostego wielokąta . Skiena napisała (str. 575, Podręcznik projektowania algorytmów), że „jest wystarczająco beznadziejna do wdrożenia, że ​​kwalifikuje się bardziej jako dowód istnienia”

Algorytm Risch do obliczania podstawowych funkcja pierwotna. Według Wikipedii żaden pakiet oprogramowania nie jest w stanie wdrożyć pełnego algorytmu ze względu na jego złożoność.

Każdy algorytm, który wykorzystuje wyniki Robertsona-Seymoura do wnioskowania o algorytmie „czasu policy” dla rzeczy obejmujących wykresy, które wykluczają ustaloną drugorzędną, prosi o kłopoty. Stałą ukrytą w ich wyniku jest „galaktyczna”.

$O(n)$$O(\frac{\log^2 n}{B})$$B$

Artykuł ma 55 stron, a jego wniosek odnotowuje kilka ulepszeń stałych, których autor nie opisuje ze względu na miejsce. To sprawia, że ​​podejrzewam, że być może stałe nie są tak galaktyczne i że ta struktura danych byłaby „uzasadnioną użytecznością”, zwłaszcza że była wielokrotnie cytowana.

Algorytm ujednolicania wzorców wyższego rzędu w linii liniowej przez Qian nigdy nie został wdrożony ze względu na jego złożoność AFAIK.

Algorytm czasu liniowego do sprawdzania, czy wykres można osadzić na stałej powierzchni.

Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed: Prostszy algorytm czasu liniowego do osadzania wykresów na powierzchni arbitralnej i rodzaju wykresów ograniczonej szerokości drzewa. FOCS 2008: 771–780.

Bojan Mohar: Algorytm czasu liniowego do osadzania wykresów na powierzchni arbitralnej. SIAM J. Discrete Math. 12 (1): 6-26 (1999)

Nie jestem pewien, jak użyteczna może być w praktyce (chociaż myślę o zwijaniu i porównywaniu białek, a także przewidywaniu struktury drugorzędowej RNA), ale Wolfgang Haken podał pierwszy algorytm czasu wielomianowego do decydowania, czy węzeł jest prosta pętla ( Theorie der Normalflächen. Acta Math. 105, 1961, s. 245--375). O ile pamiętam, wciąż jest zbyt skomplikowany, aby wdrożyć go przez te wszystkie dekady później.

Jeśli wierzyć Wikipedii, później podano kilka innych algorytmów, a „Zrozumienie złożoności tych algorytmów jest aktywnym obszarem badań”.

Rozkład drzew i być może sterty Fibonacciego .

Idealna konstrukcja skrótu ( https://en.wikipedia.org/wiki/Perfect_hash_function#Construction ) miałaby zastosowanie do każdego przypadku użycia ze statycznymi lub rzadko zmieniającymi się kluczami (np. Nazwy domen najwyższego poziomu na routerach, słowa kluczowe w kompilatorach lub nazwy funkcji w bibliotekach standardowych), ale kiedy ostatnio szukałem, nie mogłem znaleźć żadnych implementacji.

Wyszukiwanie parametryczne może rozwiązać wiele trudnych problemów związanych z optymalizacją, w tym niektóre, które mogą wyglądać na trudne NP, w czasie wielomianowym. Dobrze nazwany artykuł Wyszukiwanie parametryczne w praktyce zaimplementował wariant wyszukiwania parametrycznego, ale nadal nie sądzę, aby został zaimplementowany w praktycznym oprogramowaniu.

$k$$n$$O(n \log n + k)$$O((n+k) \log n)$