Hacker News new | ask | show | jobs
by jey 5957 days ago
In the real world, problem \in P isn't that enlightening. The constant factors matter.

I haven't looked into modern computational complexity research a whole lot, but I suspect it gets a disproportionate amount of attention because of the historical successes and importance of the field. Kind of like particle accelerators and NASA.

1 comments

I would just like to point that constants are rarely the important point. Exponents are a huge deal. A lot of things are possible and fast because FFT is N log N versus N^2.