Escrever um algoritmo para calcular a Transformada Discreta de Fourier de um vetor de dimensão
em
operações aritméticas, onde
, ou mostrar que isso não pode ser feito.
Passo 1
O enunciado pede um algoritmo que compute a Transformada Discreta de Fourier (DFT) de um vetor de tamanho
usando
operações aritméticas, com
ou, em vez de dar tal algoritmo, mostrar que não é possível. O conteúdo envolve a complexidade aritmética da DFT e possíveis limites inferiores para esta transformação linear invertível.
Passo 2
O melhor algoritmo clássico para a DFT é o Cooley–Tukey FFT, que executa em
operações (somas e multiplicações de números complexos). Logo, até hoje não conhecemos nenhum método que faça a DFT em
.
Passo 3
Para provar que não existe algoritmo em
teríamos de estabelecer um limite inferior não trivial para a DFT no modelo de complexidade aritmética. Entretanto, apesar de vários esforços em teoria da complexidade algébrica, não há até hoje nenhuma prova de que
Em particular, não se conseguiu reduzir a ordenação (que tem limite
em comparações) à DFT de modo a herdar esse limite, nem demonstrar um argumento de contagem de graus de liberdade que force o fator
.
Passo 4
Todos os resultados de limite inferior conhecidos para transformadas bilineares como a DFT são fracos: por exemplo, provam apenas que
, mas deixam a porta aberta para
. Do lado algorítmico, também não há proposta concreta de acelerar o FFT até um custo estritamente menor que
.
Passo 5
Como não conhecemos nem algoritmo em
nem prova de que isso seja impossível, o problema é aberto na teoria da complexidade algébrica.
Resposta
Atualmente não se sabe construir um algoritmo para DFT com
nem se pode provar que tal algoritmo seja impossível. Esse caso permanece como um problema em aberto.