Escrever um algoritmo para calcular a Transformada Discreta de Fourier de um vetor de dimensão N em T(N) operações aritméticas, onde lim T infty T(N)N log 2(N)=0, 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 N usando T(N) operações aritméticas, com
limN to inftyT(N)Nlog2N=0,
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
TFFT(N)=Ol(Nlog2Nr)
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 o(Nlog N).

Passo 3

Para provar que não existe algoritmo em o(Nlog N) 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
T(N)=Omegal(Nlog Nr)
Em particular, não se conseguiu reduzir a ordenação (que tem limite Omega(Nlog N) em comparações) à DFT de modo a herdar esse limite, nem demonstrar um argumento de contagem de graus de liberdade que force o fator log N.

Passo 4

Todos os resultados de limite inferior conhecidos para transformadas bilineares como a DFT são fracos: por exemplo, provam apenas que T(N)=Omega(N), mas deixam a porta aberta para T(N)=o(Nlog N). Do lado algorítmico, também não há proposta concreta de acelerar o FFT até um custo estritamente menor que O(Nlog N).

Passo 5

Como não conhecemos nem algoritmo em o(Nlog N) 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
T(N)=ol(Nlog2Nr),
nem se pode provar que tal algoritmo seja impossível. Esse caso permanece como um problema em aberto.

Exercícios de Livros Relacionados