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

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

Возможные варианты использования

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

Алгоритм, даже если он непрактичен, может показать новые методы, которые в конечном итоге могут быть использованы для создания практических алгоритмов.
Доступная вычислительная мощность может достичь точки пересечения, и ранее непрактичный алгоритм станет практичным.
Непрактичный алгоритм все же может продемонстрировать, что предполагаемые границы могут быть достигнуты или что предложенные границы неверны, и, следовательно, продвинуть теорию алгоритмов. Как утверждает Липтон: ^[1]
Уже одно это может быть важно и часто является веской причиной для поиска таких алгоритмов. Например, если бы завтра произошло открытие, которое показало бы, что существует алгоритм факторинга с огромной, но доказуемо полиномиальной границей времени, это изменило бы наши представления о факторинге. Алгоритм, возможно, никогда не будет использован, но он, безусловно, повлияет на будущие исследования факторинга.
Аналогично, гипотетическая большая, но полиномиальная $O{\bigl (}n^{2^{100}}{\bigr )}$ Алгоритм решения булевой проблемы выполнимости , хотя и непригоден для использования на практике, позволил бы решить проблему P и NP , считающуюся наиболее важной открытой проблемой в информатике и одной из проблем Премии тысячелетия . ^[2]

Примеры

Целочисленное умножение

Примером галактического алгоритма является самый быстрый из известных способов умножения двух чисел . ^[3] который основан на 1729-мерном преобразовании Фурье . ^[4] Это требует $O(n\log n)$ битовые операции, но поскольку константы, скрытые за большой буквой O , велики, на практике они никогда не используются. Однако это также показывает, почему галактические алгоритмы все еще могут быть полезны. Авторы заявляют: «Мы надеемся, что при дальнейших усовершенствованиях алгоритм может стать практичным для чисел, состоящих всего лишь из миллиардов или триллионов цифр». ^[4]

Умножение матрицы

Первое улучшение по сравнению с матричным умножением методом грубой силы (которое требует $O(n^{3})$ умножения) был алгоритм Штрассена : рекурсивный алгоритм, который требует $O(n^{2.807})$ умножения. Этот алгоритм не является галактическим и используется на практике. Дальнейшим расширением этого подхода с использованием сложной теории групп являются алгоритм Копперсмита-Винограда и его несколько лучшие последователи, требующие $O(n^{2.373})$ умножения. Они галактические: «Тем не менее, мы подчеркиваем, что такие улучшения представляют лишь теоретический интерес, поскольку огромные константы, связанные со сложностью быстрого умножения матриц, обычно делают эти алгоритмы непрактичными». ^[5]

Пропускная способность канала связи

Клод Шеннон показал простой, но асимптотически оптимальный код , способный достичь теоретической пропускной способности канала связи . Это требует присвоения случайного кодового слова каждому возможному $n$ -битное сообщение, затем декодирование путем нахождения ближайшего кодового слова. Если $n$ выбирается достаточно большим, это превосходит любой существующий код и может быть сколь угодно близко к пропускной способности канала. К сожалению, любой $n$ достаточно большой, чтобы превзойти существующие кодексы, также совершенно непрактично. ^[6] Эти коды, хотя никогда и не использовались, вдохновили на десятилетия исследований более практичных алгоритмов, которые сегодня могут достигать скоростей, сколь угодно близких к пропускной способности канала. ^[7]

Подграфы

Проблема определения того, является ли граф $G$ содержит $H$ как минор, , но где NP-полна вообще говоря, $H$ фиксирована, ее можно решить за полиномиальное время. Время работы для проверки того, $H$ является несовершеннолетним из $G$ в этом случае $O(n^{2})$ , ^[8] где $n$ это количество вершин в $G$ а большое обозначение O скрывает константу, которая суперэкспоненциально зависит от $H$ . Константа больше, чем $2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))$ в обозначении Кнута, направленном вверх , где $h$ это количество вершин в $H$ . ^[9] Даже случай $h=4$ не может быть разумно вычислено, поскольку константа больше 2, тетрадного на 65536, то есть ${^{65536}2=\ \atop {\ }}{{\underbrace {2^{2^{\cdot ^{\cdot ^{2}}}}} } \atop 65536}$ .

Криптографические взломы

На криптографическом жаргоне «взлом» — это любая ожидаемая атака, более быстрая, чем грубая сила , то есть выполнение одной пробной расшифровки для каждого возможного ключа. Для многих криптографических систем взломы известны, но при нынешних технологиях они практически невозможны. Одним из примеров является лучшая известная атака на 128-битный AES , которая требует всего $2^{126}$ операции. ^[10] Несмотря на свою непрактичность, теоретические взломы могут дать представление о закономерностях уязвимостей, а иногда и привести к обнаружению уязвимостей, которые можно использовать.

Задача коммивояжера

В течение нескольких десятилетий самым известным приближением к задаче коммивояжера в метрическом пространстве был очень простой алгоритм Кристофидеса , который давал путь не более чем на 50% длиннее оптимального. (Многие другие алгоритмы обычно могли бы работать намного лучше, но это невозможно доказать.) В 2020 году был обнаружен новый и гораздо более сложный алгоритм, который может превзойти этот показатель. $10^{-34}$ процент. ^[11] Хотя никто никогда не перейдет на этот алгоритм из-за его очень незначительного улучшения в худшем случае, он по-прежнему считается важным, потому что «это незначительное улучшение позволяет преодолеть как теоретический, так и психологический затор». ^[12]

Поиск Хаттера

Один алгоритм «Поиск Хаттера» может решить любую четко определенную задачу за асимптотически оптимальное время, за исключением некоторых оговорок. Он работает путем поиска всех возможных алгоритмов (по времени выполнения) и одновременного поиска всех возможных доказательств (по длине доказательства), ища доказательство правильности для каждого алгоритма. Поскольку доказательство правильности имеет конечный размер, оно «только» добавляет константу и не влияет на асимптотическое время выполнения. Однако эта константа настолько велика, что алгоритм совершенно непрактичен. ^[13]^[14] Например, если кратчайшее доказательство правильности данного алгоритма имеет длину 1000 бит, при поиске будут проверены как минимум 2 ⁹⁹⁹ в первую очередь другие потенциальные доказательства.

Поиск Хаттера связан с индукцией Соломонова , которая является формализацией байесовского вывода. Все вычислимые теории (реализованные программами), которые идеально описывают предыдущие наблюдения, используются для расчета вероятности следующего наблюдения, при этом больший вес придается более коротким вычислимым теориям. Опять же, перебор всех возможных объяснений делает эту процедуру галактической.

Оптимизация

имитация отжига Доказано, что при использовании с логарифмическим графиком охлаждения позволяет найти глобальный оптимум для любой задачи оптимизации. Однако такой график охлаждения приводит к совершенно непрактичному времени работы и никогда не используется. ^[15] Однако знание о существовании этого идеального алгоритма привело к появлению практических вариантов, которые способны находить очень хорошие (хотя и не доказуемо оптимальные) решения сложных задач оптимизации. ^[16]

Минимальные связующие деревья

Алгоритм MST с ожидаемым линейным временем способен обнаружить минимальное остовное дерево графа в $O(m+n)$ , где $m$ количество ребер и $n$ — количество узлов графа. ^[17] Однако постоянный коэффициент, скрытый за обозначением Big O, достаточно велик, чтобы сделать алгоритм непрактичным. Реализация общедоступна ^[18] и учитывая экспериментально оцененные константы реализации, он будет быстрее алгоритма Борувки только для графов, в которых $m+n>9\cdot 10^{151}$ . ^[19]

Хэш-таблицы

Исследователи нашли алгоритм, который достигает доказуемо наилучшего возможного результата. ^[20] асимптотическая производительность с точки зрения компромисса времени и пространства. ^[21] Но это остается чисто теоретическим: «Несмотря на беспрецедентную эффективность новой хеш-таблицы, вряд ли кто-то попытается построить ее в ближайшее время. Ее слишком сложно построить». ^[22] и «на практике константы действительно имеют значение. В реальном мире коэффициент 10 — это конец игры». ^[23]

Ссылки

^ Jump up to: ^а ^б Липтон, Ричард Дж .; Риган, Кеннет В. (2013). «Дэвид Джонсон: Галактические алгоритмы» . Люди, проблемы и доказательства: Очерки из утраченного письма Гёделя: 2010 . Гейдельберг: Springer Berlin. стр. 109–112. ISBN 9783642414220 .
^ Фортнау, Л. (2009). «Состояние проблемы P и NP» (PDF) . Коммуникации АКМ . 52 (9): 78–86. дои : 10.1145/1562164.1562186 . S2CID 5969255 .
^ Дэвид, Харви; Хувен, Йорис ван дер (март 2019 г.). «Умножение целых чисел за время O(n log n)» . ХЭЛ . hal-02070778.
^ Jump up to: ^а ^б Харви, Дэвид (9 апреля 2019 г.). «Мы нашли более быстрый способ умножать действительно большие числа» . Разговор . Проверено 9 марта 2023 г.
^ Ле Галл, Ф. (2012), «Быстрые алгоритмы умножения прямоугольных матриц», Труды 53-го ежегодного симпозиума IEEE по основам информатики (FOCS 2012) , стр. 514–523, arXiv : 1204.1111 , doi : 10.1109/FOCS .2012.80 , ISBN 978-0-7695-4874-6 , S2CID 2410545
^ Ларри Хардести (19 января 2010 г.). «Объяснение: предел Шеннона» . Пресс-служба Массачусетского технологического института.
^ «Коды, приближающиеся к пропускной способности (Глава 13 Принципов цифровой связи II )» (PDF) . MIT OpenCourseWare . 2005.
^ Каварабаяси, Кен-ичи; Кобаяши, Юсуке; Рид, Брюс (2012). «Задача о непересекающихся путях в квадратичном времени» . Журнал комбинаторной теории . Серия Б. 102 (2): 424–435. дои : 10.1016/j.jctb.2011.07.004 .
^ Джонсон, Дэвид С. (1987). «Колонка NP-полноты: постоянное руководство (выпуск 19)». Журнал алгоритмов . 8 (2): 285–303. CiteSeerX 10.1.1.114.3864 . дои : 10.1016/0196-6774(87)90043-5 .
^ Бяошуай Тао и Хунцзюнь Ву (2015). Информационная безопасность и конфиденциальность . Конспекты лекций по информатике. Том. 9144. стр. 39–56. дои : 10.1007/978-3-319-19962-7_3 . ISBN 978-3-319-19961-0 .
^ Анна Р. Карлин; Натан Кляйн; Шаян Овейс Гаран (1 сентября 2020 г.). «(Немного) улучшенный алгоритм аппроксимации для метрического TSP». arXiv : 2007.01409 [ cs.DS ].
^ Кларрайх, Эрика (8 октября 2020 г.). «Учёные-компьютерщики побили рекорд коммивояжёра» . Журнал Кванта .
^ Хаттер, Маркус (14 июня 2002 г.). «Самый быстрый и кратчайший алгоритм для всех четко определенных задач». arXiv : cs/0206022 .
^ Гальоло, Маттео (20 ноября 2007 г.). «Универсальный поиск» . Схоларпедия . 2 (11): 2575. Бибкод : 2007SchpJ...2.2575G . doi : 10.4249/scholarpedia.2575 . ISSN 1941-6016 .
^ Лян, Слава; Ченг, Ичен; Линь, Гуан (2014). «Моделирование стохастического аппроксимационного отжига для глобальной оптимизации с графиком охлаждения с квадратным корнем». Журнал Американской статистической ассоциации . 109 (506): 847–863. дои : 10.1080/01621459.2013.872993 . S2CID 123410795 .
^ Ингбер, Лестер (1993). «Имитированный отжиг: практика против теории» . Математическое и компьютерное моделирование . 18 (11): 29–57. CiteSeerX 10.1.1.15.1046 . дои : 10.1016/0895-7177(93)90204-C .
^ Каргер, Дэвид Р.; Кляйн, Филип Н.; Тарьян, Роберт Э. (1 марта 1995 г.). «Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев» . Журнал АКМ . 42 (2): 321–328. дои : 10.1145/201019.201022 . ISSN 0004-5411 .
^ Тизен, Франциско. «Реализация C++ для алгоритма минимального остовного дерева с ожидаемым линейным временем (проверка минимального остовного дерева Каргера-Кляйна-Тарджана + Хагерупа как подпрограмма)» . Гитхаб . Проверено 19 ноября 2022 г.
^ Гейман Тизен, Франциско. «Ожидаемые минимальные остовные деревья за линейное время» . franciscothiesen.github.io . Проверено 13 ноября 2022 г.
^ Тяньсяо Ли, Цзинсюнь Лян, Хуачэн Юй и Жэньфэй Чжоу. «Точные нижние границы клеточного зонда для динамических кратких словарей» (PDF) . {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Бендер, Майкл; Фарах-Колтон, Мартин; Кушмаул, Джон; Кушмаул, Уильям; Минмоу, Лю (4 ноября 2021 г.). «Об оптимальном соотношении времени и пространства для хеш-таблиц». arXiv : 2111.00602 [ CS ].
^ «Ученые нашли оптимальный баланс хранения данных и времени» .
^ Уильям Кушмаул, цитируется в «Ученые нашли оптимальный баланс хранения данных и времени» .

[seminal-1] Jump up to: ^а ^б Липтон, Ричард Дж .; Риган, Кеннет В. (2013). «Дэвид Джонсон: Галактические алгоритмы» . Люди, проблемы и доказательства: Очерки из утраченного письма Гёделя: 2010 . Гейдельберг: Springer Berlin. стр. 109–112. ISBN 9783642414220 .

[2] Фортнау, Л. (2009). «Состояние проблемы P и NP» (PDF) . Коммуникации АКМ . 52 (9): 78–86. дои : 10.1145/1562164.1562186 . S2CID 5969255 .

[3] Дэвид, Харви; Хувен, Йорис ван дер (март 2019 г.). «Умножение целых чисел за время O(n log n)» . ХЭЛ . hal-02070778.

[quick-4] Jump up to: ^а ^б Харви, Дэвид (9 апреля 2019 г.). «Мы нашли более быстрый способ умножать действительно большие числа» . Разговор . Проверено 9 марта 2023 г.

[5] Ле Галл, Ф. (2012), «Быстрые алгоритмы умножения прямоугольных матриц», Труды 53-го ежегодного симпозиума IEEE по основам информатики (FOCS 2012) , стр. 514–523, arXiv : 1204.1111 , doi : 10.1109/FOCS .2012.80 , ISBN 978-0-7695-4874-6 , S2CID 2410545

[6] Ларри Хардести (19 января 2010 г.). «Объяснение: предел Шеннона» . Пресс-служба Массачусетского технологического института.

[7] «Коды, приближающиеся к пропускной способности (Глава 13 Принципов цифровой связи II )» (PDF) . MIT OpenCourseWare . 2005.

[kkr12-8] Каварабаяси, Кен-ичи; Кобаяши, Юсуке; Рид, Брюс (2012). «Задача о непересекающихся путях в квадратичном времени» . Журнал комбинаторной теории . Серия Б. 102 (2): 424–435. дои : 10.1016/j.jctb.2011.07.004 .

[9] Джонсон, Дэвид С. (1987). «Колонка NP-полноты: постоянное руководство (выпуск 19)». Журнал алгоритмов . 8 (2): 285–303. CiteSeerX 10.1.1.114.3864 . дои : 10.1016/0196-6774(87)90043-5 .

[:0-10] Бяошуай Тао и Хунцзюнь Ву (2015). Информационная безопасность и конфиденциальность . Конспекты лекций по информатике. Том. 9144. стр. 39–56. дои : 10.1007/978-3-319-19962-7_3 . ISBN 978-3-319-19961-0 .

[11] Анна Р. Карлин; Натан Кляйн; Шаян Овейс Гаран (1 сентября 2020 г.). «(Немного) улучшенный алгоритм аппроксимации для метрического TSP». arXiv : 2007.01409 [ cs.DS ].

[12] Кларрайх, Эрика (8 октября 2020 г.). «Учёные-компьютерщики побили рекорд коммивояжёра» . Журнал Кванта .

[13] Хаттер, Маркус (14 июня 2002 г.). «Самый быстрый и кратчайший алгоритм для всех четко определенных задач». arXiv : cs/0206022 .

[14] Гальоло, Маттео (20 ноября 2007 г.). «Универсальный поиск» . Схоларпедия . 2 (11): 2575. Бибкод : 2007SchpJ...2.2575G . doi : 10.4249/scholarpedia.2575 . ISSN 1941-6016 .

[15] Лян, Слава; Ченг, Ичен; Линь, Гуан (2014). «Моделирование стохастического аппроксимационного отжига для глобальной оптимизации с графиком охлаждения с квадратным корнем». Журнал Американской статистической ассоциации . 109 (506): 847–863. дои : 10.1080/01621459.2013.872993 . S2CID 123410795 .

[16] Ингбер, Лестер (1993). «Имитированный отжиг: практика против теории» . Математическое и компьютерное моделирование . 18 (11): 29–57. CiteSeerX 10.1.1.15.1046 . дои : 10.1016/0895-7177(93)90204-C .

[17] Каргер, Дэвид Р.; Кляйн, Филип Н.; Тарьян, Роберт Э. (1 марта 1995 г.). «Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев» . Журнал АКМ . 42 (2): 321–328. дои : 10.1145/201019.201022 . ISSN 0004-5411 .

[18] Тизен, Франциско. «Реализация C++ для алгоритма минимального остовного дерева с ожидаемым линейным временем (проверка минимального остовного дерева Каргера-Кляйна-Тарджана + Хагерупа как подпрограмма)» . Гитхаб . Проверено 19 ноября 2022 г.

[19] Гейман Тизен, Франциско. «Ожидаемые минимальные остовные деревья за линейное время» . franciscothiesen.github.io . Проверено 13 ноября 2022 г.

[20] Тяньсяо Ли, Цзинсюнь Лян, Хуачэн Юй и Жэньфэй Чжоу. «Точные нижние границы клеточного зонда для динамических кратких словарей» (PDF) . {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )

[21] Бендер, Майкл; Фарах-Колтон, Мартин; Кушмаул, Джон; Кушмаул, Уильям; Минмоу, Лю (4 ноября 2021 г.). «Об оптимальном соотношении времени и пространства для хеш-таблиц». arXiv : 2111.00602 [ CS ].

[22] «Ученые нашли оптимальный баланс хранения данных и времени» .

[23] Уильям Кушмаул, цитируется в «Ученые нашли оптимальный баланс хранения данных и времени» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]