The fastest and shortest algorithm for all well-defined problems (2002)

Re:The fastest and shortest algorithm for all well-defined p... by klyrs on Wednesday May 26, 2021 @11:54AM (#27292132)

Computer science was a new branch of mathematics 100 years ago. Folks discovered the easy, low-lying algorithms. I don't know about you, but I've rediscovered quite old results that are named so-and-so's algorithm or what's-their-face's theorem; because they were the obviously efficient ways of solving those problems.

Supposing P=NP, one would expect the polytime algorithm to be brain-meltingly complex. Same goes for, say, a n^2log(n) matrix multiplication algorithm.

Simplification is a really good strategy for optimizing algorithms. But sometimes, doing less work requires doing a bit of thinking upfront, or carefully cleaning up behind yourself (but not cleaning too eagerly).

[ Parent | on HN ]

Re:The fastest and shortest algorithm for all well-defined p... by asimpletune on Wednesday May 26, 2021 @11:59AM (#27292210)

I really don’t understand why this is being downvoted. Beyond trivial algorithms, as mentioned in the parent, fast algorithms come from deep knowledge of the problem, leading to highly tailored data structures, and thus very complicated algorithms. I’m not sure why this is controversial? Also citing aesthetic sensibility is fine, but it’s also fine to update or recalibrate one’s aesthetic intuition.

[ Parent | on HN ]