Сложность свертки в кольце max / plus

10

Мы можем сделать свертку в для полиномов плюс / умножение с FFT. Тем не менее, подход не кажется очень обобщенным для колец в целом. Был ли какой-нибудь прогресс по наивной свертке для кольца max / plus?О(NжурналN)О(N2)

Я должен отметить, что можно преобразовать soft-max / plus в plus / product, выполняя возведение в степень. Здесь .soft-max(Икс,Y)знак равножурнал(еИкс+еY)знак равноМаксимум(Икс,Y)+журнал(1+емин(Икс,Y)-Максимум(Икс,Y))

Томас Але
источник
1
@ChaoXu комментарий -> ответ?
Сашо Николов

Ответы:

11

Есть более общий вопрос о mathoverflow .

Я задал подобный вопрос о CS.SE . Jbapple предоставил хороший ответ. Цитировать

«Ожерелья, свертки и X + Y», Bremner et al. показывает алгоритм для этой задачи на реальной оперативной памяти и алгоритм в модели неоднородного линейного дерева решений.О(N2(Л.Г.Л.Г.N)3Л.Г.2N)О(NN)

Любое улучшение этой границы позволит пролить свет на несколько жестких открытых проблем, таких как сортировка и кратчайший путь всех пар.Икс+Y

Если одна из функций является выпуклой / вогнутой, мы можем решить задачу за времени. См. «Ускорение динамического программирования», Eppstein et al. ,О(NжурналN)

Чао Сюй
источник
1
Спасибо. Я также с удовольствием читал об этом по ссылке mathoverflow.
Томас Але
Мне интересно, может ли "монотонно увеличиваться" быть полезным свойством.
Томас Але
2
Первая проблема, которую авторы пытаются решить в статье «Ожерелья», монотонно возрастает. Вероятно, нет известного алгоритма, который работает лучше, чем в общем случае.
Чао Сюй