Today I read about P and NP. I started with the informal discussion of the topic in Math Games with Bad Drawings by Ben Orlin, which I got for my birthday last week. Then I read the somewhat more technical overview in Introduction to Algorithms by Thomas H. Cormen et al., a beautiful, big book that I’ve been lugging around since college. Then I looked at some of the discussion of the topic in The Princeton Companion to Mathematics (an even bigger, more beautiful book). It was good to refresh my memory on this fundamental of computer science, which was my college minor.
For those unaware, P and NP are classes of problems, divided based on how difficult they appear to be to solve. Problems in P can be thought of as those that will take a computer a reasonable length of time to solve. Problems in NP are those that, using any known algorithm, will take a computer an unreasonable length of time to solve. The relationship between P and NP is an unsolved problem in mathematics. (Are they actually different?) Something I thought was interesting, though, was Ben Orlin’s comment that humans seem to be very attracted to problems in NP. Many of our games and puzzles fall into that class.