Quote:
Originally Posted by LaurV
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
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.