Złożoność splotu w pierścieniu max / plus

Możemy wykonać splot w $O(n\log n)$ dla wielomianów dodatnich / wielokrotnych za pomocą FFT. Jednak podejście to nie wydaje się zbyt ogólne w odniesieniu do pierścieni w ogóle. Czy nastąpił postęp w stosunku do naiwnego splotu $O(n^2)$ dla pierścienia max / plus?

$\text{soft-max}(x,y)=\log(e^x+e^y) = \max(x,y) + \log(1+e^{\min(x,y)-\max(x,y)})$

Istnieje bardziej ogólne pytanie dotyczące przepływu matematyki .

Zadałem podobne pytanie na CS.SE . jbapple podał dobrą odpowiedź. Cytować

„Naszyjniki, zwoje i X + Y”, Bremner i in. pokazuje algorytm $O\left(\frac{n^2(\lg \lg n)^3}{\lg^2 n}\right)$ dla tego problemu na prawdziwej pamięci RAM i $O(n \sqrt{n})$ w niejednorodnym modelu liniowego drzewa decyzyjnego.

Wszelkie ulepszenia tego ograniczenia rzucą światło na kilka trudnych otwartych problemów, takich jak sortowanie i wszystkie najkrótsze ścieżki.$X+Y$

Jeśli jedna z funkcji jest wypukła / wklęsła, możemy rozwiązać problem w czasie . Patrz „Przyspieszenie programowania dynamicznego”, Eppstein i in. .$O(n\log n)$