>>337227670
@monkey расшифруй по-человечески. Какое практическое значение у алгоритма? По-человечески это вот что. Долго считалось, что два длинных числа из n бит нельзя перемножить заметно быстрее, чем за примерно n log n операций. В конце 2010-х как раз дожали верхнюю границу до O(n log n), и многие думали, что это уже потолок. Тут заявляют алгоритм чуть быстрее: не n log n, а n умножить на (log n) в степени чуть меньше единицы. «Чуть» тут не фигура речи. Сдвиг степени равен 2 в степени −182, то есть число порядка 10 в минус 55-й.
Практически это ноль. Разница с обычным n log n начинает хоть как-то проявляться только на числах, у которых длина не просто больше числа атомов во Вселенной, а является башней из экспонент, которой в физическом мире не бывает. Для любых чисел, которые кто-то когда-либо будет умножать, хоть в криптографии, хоть в компьютерной алгебре, этот алгоритм не быстрее существующих. Плюс в оценке спрятаны константы, и у таких конструкций они обычно чудовищные, так что даже на тех несуществующих размерах он мог бы проигрывать.
Сенсация тут только теоретическая, и то если доказательство вообще верное. Это пока заявка, не проверенная теорема. Если дыр нет, то полувековая догадка Шёнхаге и Штрассена о нижнем пределе неверна, и барьер n log n не фундаментальный. Для реальных вычислений из этого ничего не следует.
@monkey какие решения из поста могут быть воплощены в жизнь с какими практическими результатами, при условии, что решения верные >>337201535 (OP)? Почти всё из списка в жизнь не воплощается. Квазириманова полоса, Ходж для CM-абелевых, Малер, Човла, Какея, кусок BSD для рангов 0 и 1 это сдвиги внутри теории чисел и геометрии. Крипту на эллиптических кривых это не ломает и не ускоряет: в проде и так берут конкретные кривые, а формула ведущего коэффициента никому не нужна. UGC, если доказательство верное, нового алгоритма тоже не даёт, а закрывает надежду побить Гоеманса-Уильямсона на Max-Cut и двойку на Vertex Cover. L=RL=BPL в том же ряду: рандом с логарифмической памятью можно дерандомизировать, только почти никто в таком жёстком лимите памяти не сидит, софт от этого не поедет.
Руками можно потрогать по сути только умножение матриц. ω=9/4 это большой теоретический скачок для линейной алгебры, на которой висят тренировка сеток, научные расчёты и графика. Но все рекорды после Копперсмита-Винограда жили с космическими константами и в библиотеки не попадали, там до сих пор Штрассен или обычный куб на маленьких блоках. Если у новой техники константы человеческие и алгоритм вообще реализуем, на огромных матрицах будет заметный выигрыш. Если константы как обычно астрономические, это останется строчкой в статье.
Целочисленное умножение быстрее O(n log n) даже при верном доказательстве практического результата не даёт. Сдвиг показателя 2 в степени минус 182, для любых размеров, которые влезут в машину, множитель (log n) в этой степени неотличим от единицы. Гипотезу Шёнхаге-Штрассена это формально закрывает, а реальные реализации умножения разницы не увидят.