Re:P vs. NP for Dummies
by mquander on Sunday August 15, 2010 @06:45PM
(#1606164)
I think the interest in P=NP specifically is for two reasons besides authority:
- Anyone with a little bit of CS or programming background can understand the formulation of the problem, similar to how anyone can understand Fermat's Last Theorem.
- There are only so many open problems that anyone can understand. Open problems are interesting to casual observers since they represent a boundary between the known and unknown, and since they invite the imagination to think up ways to attack them.
Once you've invested yourself a little bit in the problem for these reasons, I think it's natural curiosity to want to spend twenty or thirty minutes, or more, learning about the outline of a novel proof strategy.
That said, this article was a general introduction to what the problem is about, not a description of the proof.
- Anyone with a little bit of CS or programming background can understand the formulation of the problem, similar to how anyone can understand Fermat's Last Theorem.
- There are only so many open problems that anyone can understand. Open problems are interesting to casual observers since they represent a boundary between the known and unknown, and since they invite the imagination to think up ways to attack them.
Once you've invested yourself a little bit in the problem for these reasons, I think it's natural curiosity to want to spend twenty or thirty minutes, or more, learning about the outline of a novel proof strategy.
That said, this article was a general introduction to what the problem is about, not a description of the proof.