NP-overrated
gruhn.me · 428 words · saved by 1 readers
NP-hard problems are solvable in theory but it's hopelessly expensive in practice. It's basically proven that no good algorithms exist.
Aug 13, 2026 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…
saved by
related reading
- P versus NP problem - Wikipediaen.wikipedia.org
- P vs. NP for Dummiesscottaaronson.blog
- pnp.pdfscottaaronson.com
- Why SAT Is Hardmatklad.github.io
- NP-completeness - Wikipediaen.wikipedia.org
- Reasons to believescottaaronson.blog
- Computational Complexity Theory (Stanford Encyclopedia of Philosophy)plato.stanford.edu
- You don't need to work on hard problems | benkuhn.netbenkuhn.net
- Complexity Theory’s 50-Year Journey to the Limits of Knowledge | Quanta Magazinequantamagazine.org
- Difference between NP hard and NP complete problem - GeeksforGeeksgeeksforgeeks.org
- Planning the best route with multiple destinations is hard even for supercomputers – a new approach breaks a barrier that’s stood for nearly half a centurytheconversation.com
- Decision problem - Wikipediaen.wikipedia.org