Complexité de la convolution dans l'anneau max / plus

10

Nous pouvons faire la convolution en pour les polynômes plus / multiplier avec FFT. Cependant, l'approche ne semble pas très généralisable aux anneaux en général. Y a-t-il eu des progrès par rapport à la convolution naïve pour l'anneau max / plus?O(nlogn)O(n2)

Je dois noter que l'on peut transformer soft-max / plus en plus / produit en faisant une exponentiation. Ici .soft-max(x,y)=log(ex+ey)=max(x,y)+log(1+emin(x,y)max(x,y))

Thomas Ahle
la source
1
Commentaire @ChaoXu -> répondre?
Sasho Nikolov

Réponses:

11

Il y a une question plus générale sur mathoverflow .

J'ai posé une question similaire sur CS.SE . jbapple a fourni une bonne réponse. Citer

"Colliers, circonvolutions et X + Y", par Bremner et al. montre un algorithme pour ce problème sur la RAM réelle et un algorithme dans le modèle d'arbre de décision linéaire non uniforme.O(n2(lglgn)3lg2n)O(nn)

Toute amélioration de cette limite mettra en lumière quelques problèmes ouverts difficiles comme le tri et le chemin le plus court de toutes les paires.X+Y

Si l'une des fonctions est convexe / concave, nous pouvons résoudre le problème en temps . Voir «Accélérer la programmation dynamique», par Eppstein et al. .O(nlogn)

Chao Xu
la source
1
Je vous remercie. J'ai également apprécié lire à ce sujet sur le lien mathoverflow.
Thomas Ahle
Je me demande si "l'augmentation monotone" pourrait être une propriété utile.
Thomas Ahle
2
Le premier problème que les auteurs tentent de résoudre dans l'article Colliers est en augmentation monotone. Il est probable qu'aucun algorithme connu ne fonctionne mieux que le cas général.
Chao Xu