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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.