Мы можем сделать свертку в для полиномов плюс / умножение с FFT. Тем не менее, подход не кажется очень обобщенным для колец в целом. Был ли какой-нибудь прогресс по наивной свертке для кольца max / plus?
Я должен отметить, что можно преобразовать soft-max / plus в plus / product, выполняя возведение в степень. Здесь .
algebra
polynomials
fft
convolution
Томас Але
источник
источник
Ответы:
Есть более общий вопрос о mathoverflow .
Я задал подобный вопрос о CS.SE . Jbapple предоставил хороший ответ. Цитировать
Любое улучшение этой границы позволит пролить свет на несколько жестких открытых проблем, таких как сортировка и кратчайший путь всех пар.Икс+ Y
Если одна из функций является выпуклой / вогнутой, мы можем решить задачу за времени. См. «Ускорение динамического программирования», Eppstein et al. ,O ( n logн )
источник