2
$\begingroup$

There are many problems which have implications on P vs. NP and other complexity classes. Supposing that we're interested in Fourier transforms and/or multiplication algorithms, do faster Fourier transforms carry any implications for P vs. NP or other complexity classes? For example, I seem to recall seeing something regarding faster matrix multiplication as it relates to P vs. NP.

I'm really trying, although I may be somewhat vague, to determine if any Fourier-related transforms have P vs. NP implications, even if we have to trace implications through several problems or complexity classes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.