Kompleksitas konvolusi pada cincin max / plus

Kita dapat melakukan konvolusi dalam untuk plus / multiplikasi polinomial dengan FFT. Namun, pendekatan itu tampaknya tidak terlalu umum untuk cincin pada umumnya. Apakah ada kemajuan selama konvolusi naif untuk cincin max / plus?$O(n\log n)$$O(n^2)$

Saya harus mencatat bahwa seseorang dapat mengubah soft-max / plus menjadi plus / produk dengan melakukan eksponensial. Di sini .$\text{soft-max}(x,y)=\log(e^x+e^y) = \max(x,y) + \log(1+e^{\min(x,y)-\max(x,y)})$

Ada pertanyaan yang lebih umum tentang mathoverflow .

Aku bertanya pertanyaan serupa di CS.SE . jbapple memberikan jawaban yang bagus. Kutipan

"Kalung, Konvolusi, dan X + Y", Oleh Bremner et al. menunjukkan algoritma untuk masalah ini pada RAM nyata dan algoritma dalam model pohon keputusan linier tidak seragam.$O\left(\frac{n^2(\lg \lg n)^3}{\lg^2 n}\right)$$O(n \sqrt{n})$

Setiap perbaikan pada ikatan ini akan menjelaskan beberapa masalah terbuka yang sulit seperti menyortir dan semua pasangan jalur terpendek.$X+Y$

Jika salah satu fungsinya cembung / cekung, kita dapat menyelesaikan masalah dalam waktu . Lihat "Mempercepat Pemrograman Dinamis", Oleh Eppstein et al. .$O(n\log n)$