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

10

Możemy wykonać splot w O(nlogn) 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(n2) dla pierścienia max / plus?

soft-max(x,y)=log(ex+ey)=max(x,y)+log(1+emin(x,y)max(x,y))

Thomas Ahle
źródło
1
@ChaoXu komentarz -> odpowiedź?
Sasho Nikolov

Odpowiedzi:

11

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(n2(lglgn)3lg2n) dla tego problemu na prawdziwej pamięci RAM i O(nn) 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(nlogn)

Chao Xu
źródło
1
Dziękuję Ci. Lubiłem też czytać o tym na linku mathoverflow.
Thomas Ahle,
Zastanawiam się, czy „monotoniczny wzrost” może być użyteczną właściwością.
Thomas Ahle,
2
Pierwszy problem, który autorzy próbują rozwiązać w artykule Naszyjniki, rośnie monotonicznie. Prawdopodobnie nie ma znanego algorytmu, który działałby lepiej niż ogólny przypadek.
Chao Xu