Post

HN
Hacker News

NP-Overrated

Ranked #3 on Hacker News with 93 points and 43 comments.

If you learned about NP-hard problems in university, your takeaway was probably this:

NP-hard problems are solvable in theory but it's hopelessly expensive in practice. It's basically proven that no good algorithms exist.

At least that's what I took away. And almost everyone I've talked to. And many people online. I keep seeing "No you can't do it. It's NP-hard. Blah blah" discussions. The myth is pervasive but these problems are not intractable.

At the time, my professor closed the final lecture with dramatic words (I'm paraphrasing slightly):

And now you've learned that almost all interesting problems are undecidable and of the remaining ones, almost all are NP-hard. For the project of computer science, that puts the final nail in the coffin.

Sheesh. Not sure if everyone got such a dire framing but that would explain.