Podemos fazer convolução em para mais / multiplicar polinômios com FFT. No entanto, a abordagem não parece muito generalizável para anéis em geral. Houve algum progresso na convolução ingênua de para o anel max / plus?
Devo observar que é possível transformar soft-max / plus em plus / product fazendo exponenciação. Aqui .
algebra
polynomials
fft
convolution
Thomas Ahle
fonte
fonte
Respostas:
Há uma pergunta mais geral sobre mathoverflow .
Pedi uma pergunta semelhante sobre CS.SE . O jbapple forneceu uma boa resposta. Citar
Qualquer melhoria nesse limite esclarecerá alguns problemas difíceis, como classificar e todos os pares de caminhos mais curtos.X+ Y
Se uma das funções for convexa / côncava, podemos resolver o problema em . Veja "Acelerando a programação dinâmica", de Eppstein et al. .O ( n logn )
fonte