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

23·3·199 Posts
Default

Quote:
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)

Quote:
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 offline