View Single Post
Old 2011-11-07, 05:17   #4
axn's Avatar
Jun 2003

19·271 Posts

Originally Posted by LaurV View Post
I would be very surprised if you found an algorithm to multiply polynomials that can be used to multiply integers in polynomial time. I really doubt. Please note that FFT multiplication is NOT polynomial. Its order is still (sub)exponential.
FFT is nlogn which is decidedly polynomial. And, the basis of FFT multiplication is polynomial multipoint evaluation (followed by pointwise multiplication)

Originally Posted by LaurV View Post
Maybe you found something like this, that could require a polynomial time, but it would require an exponential space.
If you require exponential space, then you need to read/write all those exponential space, and therefore your algo is exponential time.
axn is online now