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

А галактический алгоритм это алгоритм, который превосходит любой другой алгоритм для задач, которые достаточно велики, но где «достаточно большой» настолько велик, что этот алгоритм никогда не используется на практике. Галактические алгоритмы были названы так Ричард Липтон и Кен Риган,^[1] поскольку они никогда не будут использоваться ни в одном из наборов чисто земных данных, которые мы находим здесь, на Земле.

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

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

• Алгоритм, даже если он непрактичен, может показать новые методы, которые в конечном итоге могут быть использованы для создания практических алгоритмов.
• Размеры компьютеров могут достигать точки пересечения, так что ранее непрактичный алгоритм становится практичным.
• Непрактичный алгоритм все же может продемонстрировать, что предполагаемые границы достижимы или что предлагаемые границы неверны. Как говорит Липтон, «это само по себе может быть важным и часто является отличной причиной для поиска таких алгоритмов. Например, если бы завтра произошло открытие, которое показало бы, что существует алгоритм факторизации с огромными, но доказуемо полиномиальными временными рамками, это изменит наши убеждения. о факторинге. Алгоритм, возможно, никогда не будет использован, но определенно определит будущие исследования факторинга ». Точно так же ${\displaystyle O\left(n^{2^{100}}\right)}$ алгоритм для Проблема логической выполнимости, хотя и непригодный для использования на практике, Проблема P против NP, наиболее важная открытая проблема в информатике и одна из Задачи Премии тысячелетия.^[5]

Примеры

Есть несколько хорошо известных алгоритмов с лучшей асимптотикой, но только для непрактично больших задач:

• Умножение матриц: первое улучшение по сравнению с умножением методом перебора, O (N³) это Алгоритм Штрассена, рекурсивный алгоритм O (N^2.807). Этот алгоритм не является галактическим и используется на практике. Дальнейшими расширениями этого с помощью сложной теории групп являются Алгоритм Копперсмита – Винограда и его немного лучше последователей, доставляющих O (N^2.373). Они галактические - «Тем не менее мы подчеркиваем, что такие улучшения представляют только теоретический интерес, поскольку огромные константы, связанные со сложностью быстрого умножения матриц, обычно делают эти алгоритмы непрактичными».^[6]
• Клод Шеннон показал простой, но непрактичный код который мог бы достичь мощности канал. Это требует присвоения случайного кодового слова каждому возможному N-битному сообщению, а затем декодирования путем нахождения ближайшего кодового слова. Если N выбрано достаточно большим, это превосходит любой существующий код и может быть сколь угодно близко к пропускной способности канала. К сожалению, любое N, достаточно большое, чтобы превзойти существующие коды, также совершенно непрактично.^[7] Эти коды, хотя они никогда не использовались, вдохновили десятилетия на исследования более практичных алгоритмов, которые сегодня могут достигать скорости, сколь угодно близкой к пропускной способности канала.^[8]
• Проблема решение ли график грамм содержит ЧАС как незначительный NP-полна вообще, но где ЧАС фиксировано, ее можно решить за полиномиальное время. Время работы для проверки того, ЧАС является несовершеннолетним из грамм в этом случае О(п²),^[9] куда п это количество вершин в грамм и нотация большой O скрывает константу, сверхэкспоненциально зависящую от ЧАС. Константа больше чем ${\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}$ (с помощью Обозначение Кнута со стрелкой вверх ), куда час это количество вершин в ЧАС.^[10]
• Для криптографов криптографический «взлом» - это что-то более быстрое, чем атака полным перебором, т.е. выполнение одного пробного дешифрования для каждого возможного ключа. Во многих случаях, даже несмотря на то, что они являются наиболее известными методами, они по-прежнему неосуществимы с использованием современных технологий. Один из примеров - лучшая известная атака против 128 бит AES, что занимает всего 2¹²⁶ операции.^[11] Несмотря на то, что теоретические исследования непрактичны, иногда они могут дать представление о моделях уязвимости.
• В течение нескольких десятилетий наиболее известное приближение к задача коммивояжера в метрическое пространство был очень простым Алгоритм Кристофидеса что дает путь максимум на 50% длиннее оптимального. (Многие другие алгоритмы могли обычно работают намного лучше, но не могут гарантировать успеха.) В 2020 году был обнаружен более новый и гораздо более сложный алгоритм, который может превзойти его в 10 раз.⁻³⁴ процентов.^[12] Хотя никто никогда не переключится на этот алгоритм для решения какой-либо реальной проблемы, он по-прежнему считается важным, потому что «это незначительное улучшение преодолевает как теоретический, так и психологический тупик».^[13]
• Существует единственный алгоритм, известный как «поиск Хаттера», который может решить любую четко определенную задачу за асимптотически оптимальное время без некоторых оговорок. Однако его скрытые константы во времени работы настолько велики, что ни для чего не пригодятся.^[14][15]

Рекомендации

1. Липтон, Ричард Дж. И Кеннет В. Риган (2013). «Дэвид Джонсон: галактические алгоритмы». Люди, проблемы и доказательства. Гейдельберг: Springer Berlin. С. 109–112.
2. Дэвид, Харви; Хувен, Йорис ван дер (март 2019 г.). «Целочисленное умножение за время O (n log n)». HAL. хал-02070778.
3. Дэвид Харви (апрель 2019 г.). «Мы нашли более быстрый способ умножать действительно большие числа». Phys.org.
4. «Мы нашли более быстрый способ умножать действительно большие числа». Цитата одного из авторов алгоритма: «Новый алгоритм не совсем практичен в его нынешнем виде, потому что доказательство, приведенное в нашей статье, работает только для смехотворно больших чисел. Даже если каждая цифра была написана на атоме водорода, там было бы недостаточно места в наблюдаемой Вселенной, чтобы записать их ".
5. Фортноу, Л. (2009). «Статус проблемы P и NP» (PDF). Коммуникации ACM. 52 (9): 78–86. Дои:10.1145/1562164.1562186.
6. Ле Галл, Ф. (2012), "Более быстрые алгоритмы умножения прямоугольных матриц", Материалы 53-го ежегодного симпозиума IEEE по основам компьютерных наук (FOCS 2012), стр. 514–523, arXiv:1204.1111, Дои:10.1109 / FOCS.2012.80
7. Ларри Хардести (19 января 2010 г.). «Разъяснение: предел Шеннона». MIT News Office.
8. «Коды приближения к емкости» (PDF).
9. Каварабаяси, К. И .; Кобаяши, Ю .; Рид, Б. (2012). «Проблема непересекающихся путей в квадратичном времени». Журнал комбинаторной теории, серия B. 102 (2): 424–435. Дои:10.1016 / j.jctb.2011.07.004.
10. Джонсон, Дэвид С. (1987). «Колонка NP-полноты: Постоянное руководство (выпуск 19)». Журнал алгоритмов. 8 (2): 285–303. CiteSeerX  10.1.1.114.3864. Дои:10.1016/0196-6774(87)90043-5.
11. Бяошуай Тао и Хунцзюнь Ву (2015). Информационная безопасность и конфиденциальность. Конспект лекций по информатике. 9144. С. 39–56. Дои:10.1007/978-3-319-19962-7_3. ISBN  978-3-319-19961-0.
12. Анна Р. Карлин; Натан Кляйн; Шаян Овейс Гаран (1 сентября 2020 г.). «(Немного) улучшенный алгоритм аппроксимации для метрической TSP». arXiv:2007.01409 [cs.DS ].
13. Эрика Кларрайх (8 октября 2020 г.). "Компьютерные ученые побили рекорд коммивояжера".
14. Хаттер, Маркус (2002-06-14). «Самый быстрый и кратчайший алгоритм для всех четко определенных задач». arXiv:cs / 0206022.
15. Гальоло, Маттео (20 ноября 2007 г.). «Универсальный поиск». Scholarpedia. 2 (11): 2575. Bibcode:2007SchpJ ... 2,2575 г. Дои:10.4249 / scholarpedia.2575. ISSN  1941-6016.