News for hackers. Stuff that matters.
Re:What if P = NP? by derefr on Friday April 01, 2011 @06:24PM (#2398353)
> For instance planar graphs cannot contain in any form 5 points that all connect to each other, nor two collections of 3 points that all connect to each other. (These are known as K5 and K3,3.)

Huh. I know this intuitively from doing those "try to connect the three houses to the three respurces without crossing any lines" kind of puzzles when I was younger—but I never made the connection that this kind of puzzle is basically the proof of the four-color theorem. My (puny) knowledge of topology has been made slightly more concrete. :)

Re:What if P = NP? by btilly on Friday April 01, 2011 @06:38PM (#2398406)
but I never made the connection that this kind of puzzle is basically the proof of the four-color theorem.

Sorry, but the proof of the four-color theorem is much, much more difficult than the proof of this result. (Which is called Kuratowski's theorem and was proved in 1930.)

See http://en.wikipedia.org/wiki/Kuratowski%27s_theorem#Kuratows... for more background on the result that I was saying, and http://people.math.gatech.edu/~thomas/FC/fourcolor.html for more on the four color theorem.