Галактический алгоритм

Галакти́ческий алгори́тм (англ. galactic algorithm) — алгоритм, превосходящий любой другой алгоритм для решения существенно больши́х задач, где «существенно большие» задачи означают настолько большой масштаб, что такой алгоритм не используется на практике. Галактические алгоритмы были так названы Ричардом Липтоном и Кеном Риганом, поскольку они никогда не будут применимы на любых «земных», привычных нам данных.

Пример галактического алгоритма — самый быстрый из известных алгоритмов умножения двух чисел, который основан на 1729-мерном преобразовании Фурье. Он не достигнет заявленной эффективности до тех пор, пока эти числа не будут иметь по крайней мере 2¹⁷²⁹¹² битов (по крайней мере 10¹⁰³⁸ цифр), что значительно превосходит число атомов в известной части Вселенной. Поэтому такой алгоритм никогда не используется на практике.

Несмотря на свою непрактичность, галактические алгоритмы могут быть полезными в теоретической информатике:

• Даже непрактичный алгоритм может продемонстрировать новые техники, которые однажды могут быть использованы для разработки практических алгоритмов.
• Объёмы данных, обрабатываемых компьютерами, могут достичь определённого значения, при котором непрактичный алгоритм становится применимым на практике.
• Непрактичный алгоритм может продемонстрировать, что предполагаемые границы могут быть достигнуты, либо что предполагаемые границы неверны. Липтон утверждает: «Это само по себе может быть важным и часто является веской причиной для поиска таких алгоритмов. Например, если бы завтра случилось открытие, доказывающее, что существует алгоритм факторизации с огромной временно́й сложностью, но достоверно полиномиальной, это бы изменило наше представление о факторизации. Сам такой алгоритм, может, никогда бы не использовался, но он показал бы пути для дальнейших исследований в этой области». Аналогично: алгоритм со сложностью $O\left(n^{2^{100}}\right)$ для решения задачи выполнимости булевых формул — хотя и неприменим на практике — решил бы проблему равенства классов P и NP, наиболее важную открытую проблему в теоретической информатике и одну из задач тысячелетия.

Примеры

Существует несколько широко известных алгоритмов с рекордной асимптотической сложностью, но лишь на непрактично крупных задачах:

• Умножение матриц: первое улучшение алгоритма со сложностью O(N³) — алгоритм Штрассена, рекурсивный алгоритм со сложностью (N^2,807). Этот алгоритм ещё не является галактическим, он используется на практике. Дальнейшие улучшения, использующие теорию групп, — алгоритм Копперсмита — Винограда и его небольшие модификации, дающие O(N^2,373), уже являются галактическими. «Мы, тем не менее, подчёркиваем, что подобные улучшения имеют сугубо теоретический интерес, поскольку огромные константы в оценках сложности быстрого умножения матриц делают их неприменимыми на практике».
• Клод Шеннон продемонстрировал простой, но непрактичный код, который мог бы достичь предела Шеннона. Он назначает случайное кодирующее слово каждому возможному N-битному сообщению, а декодирование происходит путём поиска наиболее похожего (с учётом искажения из-за шумов) кодирующего слова. Если выбранное N достаточно велико, то алгоритм превосходит любой другой и может сколь угодно близко приближаться к пределу Шеннона. К сожалению, любое достаточно большое N, при котором это возможно, делает такой подход непрактичным. Такой способ кодирования, хотя и не используется на практике, подтолкнул к длительному изучению более практичных алгоритмов, которые на сегодняшний день произвольно близко приближаются к пределу Шеннона.
• Задача разрешимости того, содержит ли граф G граф H в качестве своего минора, является NP-полной в общем случае, но если H фиксировано, она может быть решена за полиномиальное время. В таком случае сложность равна O(n²), где n — это число вершин в графе G, а асимптотическая нотация скрывает константу, которая сверх-экспоненциально зависит от H. Эта константа превосходит $2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))$ (используется стрелочная нотация Кнута), где h — это число вершин в графе H.
• В криптографии «взломом» является любое решение, которое работает быстрее, чем атака с помощью полного перебора. Во многих случаях, даже если эти алгоритмы «взлома» являются наилучшими среди известных, они всё равно недостижимы при текущем уровне развития технологий. Одним из примеров является атака на 128-битный алгоритм AES, требующая только 2¹²⁶ операций. Несмотря на непрактичность, теоретические схемы взлома могут натолкнуть на идеи для реального взлома.
• В течение нескольких десятилетий лучшим известным приближённым решением задачи коммивояжёра в метрическом пространстве был довольно простой алгоритм Кристофидеса, который производил путь в худшем случае на 50 процентов длиннее оптимального. (Многие другие алгоритмы, как правило, справлялись лучше, но не могли гарантировать результат.) В 2020 опубликован более сложный алгоритм, чей результат лучше на 10⁻³⁴ процентов. Хотя никто не станет переходить на него на практике, он считается важным, поскольку «это небольшое улучшение позволяет преодолеть и теоретический барьер, и психологический».
• Существует единственный алгоритм, известный как «поиск Хаттера», который способен решить любую строго определённую задачу за асимптотически оптимальное время, кроме некоторых случаев. Однако скрытые константы в оценке временно́й сложности столько велики, что он никогда не станет пригодным на практике.