Русская Википедия:Галактический алгоритм
Галакти́ческий алгори́тм (Шаблон:Lang-en) — алгоритм, превосходящий любой другой алгоритм для решения существенно больши́х задач, где «существенно большие» задачи означают настолько большой масштаб, что такой алгоритм не используется на практике. Галактические алгоритмы были так названы Ричардом Липтоном и Кеном Риганом[1], поскольку они никогда не будут применимы на любых «земных», привычных нам данных.
Пример галактического алгоритма — самый быстрый из известных алгоритмов умножения двух чисел[2], который основан на 1729-мерном преобразовании Фурье[3]. Он не достигнет заявленной эффективности до тех пор, пока эти числа не будут иметь по крайней мере 2172912 битов (по крайней мере 101038 цифр), что значительно превосходит число атомов в известной части Вселенной. Поэтому такой алгоритм никогда не используется на практике[4].
Несмотря на свою непрактичность, галактические алгоритмы могут быть полезными в теоретической информатике:
- Даже непрактичный алгоритм может продемонстрировать новые техники, которые однажды могут быть использованы для разработки практических алгоритмов.
- Объёмы данных, обрабатываемых компьютерами, могут достичь определённого значения, при котором непрактичный алгоритм становится применимым на практике.
- Непрактичный алгоритм может продемонстрировать, что предполагаемые границы могут быть достигнуты, либо что предполагаемые границы неверны. Липтон утверждает: «Это само по себе может быть важным и часто является веской причиной для поиска таких алгоритмов. Например, если бы завтра случилось открытие, доказывающее, что существует алгоритм факторизации с огромной временно́й сложностью, но достоверно полиномиальной, это бы изменило наше представление о факторизации. Сам такой алгоритм, может, никогда бы не использовался, но он показал бы пути для дальнейших исследований в этой области». Аналогично: алгоритм со сложностью <math>O\left(n^{2^{100}}\right)</math> для решения задачи выполнимости булевых формул — хотя и неприменим на практике — решил бы проблему равенства классов P и NP, наиболее важную открытую проблему в теоретической информатике и одну из задач тысячелетия[5].
Примеры
Существует несколько широко известных алгоритмов с рекордной асимптотической сложностью, но лишь на непрактично крупных задачах:
- Умножение матриц: первое улучшение алгоритма со сложностью O(N3) — алгоритм Штрассена, рекурсивный алгоритм со сложностью (N2,807). Этот алгоритм ещё не является галактическим, он используется на практике. Дальнейшие улучшения, использующие теорию групп, — алгоритм Копперсмита — Винограда и его небольшие модификации, дающие O(N2,373), уже являются галактическими. «Мы, тем не менее, подчёркиваем, что подобные улучшения имеют сугубо теоретический интерес, поскольку огромные константы в оценках сложности быстрого умножения матриц делают их неприменимыми на практике»[6].
- Клод Шеннон продемонстрировал простой, но непрактичный код, который мог бы достичь предела Шеннона. Он назначает случайное кодирующее слово каждому возможному N-битному сообщению, а декодирование происходит путём поиска наиболее похожего (с учётом искажения из-за шумов) кодирующего слова. Если выбранное N достаточно велико, то алгоритм превосходит любой другой и может сколь угодно близко приближаться к пределу Шеннона. К сожалению, любое достаточно большое N, при котором это возможно, делает такой подход непрактичным[7]. Такой способ кодирования, хотя и не используется на практике, подтолкнул к длительному изучению более практичных алгоритмов, которые на сегодняшний день произвольно близко приближаются к пределу Шеннона[8].
- Задача разрешимости того, содержит ли граф G граф H в качестве своего минора, является NP-полной в общем случае, но если H фиксировано, она может быть решена за полиномиальное время. В таком случае сложность равна O(n2)[9], где n — это число вершин в графе G, а асимптотическая нотация скрывает константу, которая сверх-экспоненциально зависит от H. Эта константа превосходит <math>2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) </math> (используется стрелочная нотация Кнута), где h — это число вершин в графе H[10].
- В криптографии «взломом» является любое решение, которое работает быстрее, чем атака с помощью полного перебора. Во многих случаях, даже если эти алгоритмы «взлома» являются наилучшими среди известных, они всё равно недостижимы при текущем уровне развития технологий. Одним из примеров является атака на 128-битный алгоритм AES, требующая только 2126 операций[11]. Несмотря на непрактичность, теоретические схемы взлома могут натолкнуть на идеи для реального взлома.
- В течение нескольких десятилетий лучшим известным приближённым решением задачи коммивояжёра в метрическом пространстве был довольно простой алгоритм Кристофидеса, который производил путь в худшем случае на 50 процентов длиннее оптимального. (Многие другие алгоритмы, как правило, справлялись лучше, но не могли гарантировать результат.) В 2020 опубликован более сложный алгоритм, чей результат лучше на 10−34 процентов[12]. Хотя никто не станет переходить на него на практике, он считается важным, поскольку «это небольшое улучшение позволяет преодолеть и теоретический барьер, и психологический»[13].
- Существует единственный алгоритм, известный как «поиск Хаттера», который способен решить любую строго определённую задачу за асимптотически оптимальное время, кроме некоторых случаев. Однако скрытые константы в оценке временно́й сложности столько велики, что он никогда не станет пригодным на практике[14][15].
Ссылки
- ↑ Шаблон:Cite Шаблон:Cite web
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite Шаблон:Cite web
- ↑ Шаблон:Cite Шаблон:Cite web Quote, from one of the authors of the algorithm: “The new algorithm is not really practical in its current form, because the proof given in our paper only works for ludicrously large numbers. Even if each digit was written on a hydrogen atom, there would not be nearly enough room available in the observable universe to write them down.”
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Citation
- ↑ Шаблон:Cite Шаблон:Cite web
- ↑ Шаблон:Cite Шаблон:Cite web
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite arxiv
- ↑ Шаблон:Cite Шаблон:Cite web
- ↑ Шаблон:Cite arxiv
- ↑ Шаблон:Cite journal