Perguntas com a marcação «fft»

16
Encontrar testemunha na soma minkowski de números inteiros

Seja e subconjuntos de . Estamos interessados ​​em encontrar a soma de Minkowski .AAABBB{0,…,n}{0,…,n}\{0,\ldots,n\}A+B={a+b | a∈A,b∈B}A+B={a+b | a∈A,b∈B}A+B=\{a+b~|~a\in A,b\in B\} χX:{0,…,2n}→{0,1}χX:{0,…,2n}→{0,1}\chi_X:\{0,\ldots,2n\}\to \{0,1\} é uma função característica de...

10
Complexidade da convolução no anel max / plus

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?O(nlogn)O(nlog⁡n)O(n\log n)O(n2)O(n2)O(n^2) Devo observar que é possível...