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

Галакти́ческий алгори́тм (англ. galactic algorithm) — алгоритм, превосходящий любой другой алгоритм для решения существенно больши́х задач, где «существенно большие» задачи означают настолько большой масштаб, что такой алгоритм не используется на практике. Галактические алгоритмы были так названы Ричардом Липтоном и Кеном Риганом, поскольку они никогда не будут применимы на любых «земных», привычных нам данных. Пример галактического алгоритма — самый быстрый из известных алгоритмов умножения двух чисел, который основан на 1729-мерном преобразовании Фурье. Он не достигнет заявленной эффективности до тех пор, пока эти числа не будут иметь по крайней мере 2172912 битов (по крайней мере 101038 цифр), что значительно превосходит число атомов в известной части Вселенной. Поэтому такой алгоритм никогда не используется на практике. Несмотря на свою непрактичность, галактические алгоритмы могут быть полезными в теоретической информатике: * Даже непрактичный алгоритм может продемонстрировать новые техники, которые однажды могут быть использованы для разработки практических алгоритмов. * Объёмы данных, обрабатываемых компьютерами, могут достичь определённого значения, при котором непрактичный алгоритм становится применимым на практике. * Непрактичный алгоритм может продемонстрировать, что предполагаемые границы могут быть достигнуты, либо что предполагаемые границы неверны. Липтон утверждает: «Это само по себе может быть важным и часто является веской причиной для поиска таких алгоритмов. Например, если бы завтра случилось открытие, доказывающее, что существует алгоритм факторизации с огромной временно́й сложностью, но достоверно полиномиальной, это бы изменило наше представление о факторизации. Сам такой алгоритм, может, никогда бы не использовался, но он показал бы пути для дальнейших исследований в этой области». Аналогично: алгоритм со сложностью для решения задачи выполнимости булевых формул — хотя и неприменим на практике — решил бы проблему равенства классов P и NP, наиболее важную открытую проблему в теоретической информатике и одну из задач тысячелетия.