Hacker News new | ask | show | jobs
by srean 3908 days ago
Polynomial time does not necessarily make it easy, the degree of the polynomial could be plenty high making large problems still sufficiently expensive.
1 comments

It need not even be of high degree. With a large enough constant, even a constant-time algorithm could be way out of reach.

Suppose that somebody shows that, once you are past a googol^googol (not a big number, as numbers in mathematics go), factoring doesn't get harder at all, that would be merely a curiosity in practice (It also would be a hugely surprising result that would inspire mathematicians to start looking for ways to bring that limit down)