Hacker News Reader

Comment by modeless | Hacker News Reader

"Malicious" is an overstatement, but "exploit" is completely fair in my view. Theory with no possible practical relevance is useless, and I think a computational complexity result requiring arbitrary-precision arithmetic that is impossible to implement using any physical system qualifies.

View on HN

Plenty of mathematics was practically useless for long periods of time, waiting for us to invent computers, cryptography, error correcting codes, etc.

It's extremely hard to know what mathematics may be useful in the future or not.

It's hard to know for certain, but that doesn't mean we should throw up our hands and say anything goes. We can still say that some things are more likely to be useful than others.

The idea that FFT's decomposition is non-optimal is surprising. What the new bound means is we basically were looking at the problem and its structure incorrectly, and therefore implicates other problems for which we have used recursion to get to our currently-best bounds. Almost no interesting math problems are just sitting there alone in their little corner. Getting a hint like that is a big deal.

Is it surprising though? If you assume constant time when it doesn't exist (in this case arbitrary precision arithmetic), it should be obvious that you will be able to devise algorithms that are faster than the commonly accepted best results.

If you can do arithmetic on arbitrarily large integers in constant time, you can sort lists in linear time.

It depends on what you're doing to the integers. You still cannot comparison-sort arbitrarily large integers in linear time.

Also, consider this: it would have been trivial to get a so-called "better bound" on FFT if such a "cheat" were what people allowed.

How can we say that without knowing the future?

Reply on news.ycombinator.com