Tag Archive for: proof

Brain exercise for half term: P vs. NP

If you’ve reached the stage of half-term where binge-watching iZombie, staring out of the window at the miserable weather, or playing yet another round of Overwatch just aren’t doing it for you, try this minor intellectual stimulation.

P vs. NP is one of the foundational problems in computer science, with a $1m bounty attached to the first correct solution. This film does a great job of setting out the problem in an understandable way, and exploring its implications.

P vs. NP is about whether every problem with a quickly verifiable solution can itself be solved quickly, which sounds like the sort of abstraction beloved only by mathematicians. But P vs. NP is related to a whole host of problems that would have very real implications if they turned out to be easier than we currently think. Encryption, for example. Or computational protein folding. And the film argues that this world of complexity problems describes not just problems in computing and mathematics, but complex problems throughout human experience.

Watch the film. Maybe get sucked into the rabbit hole of Wikipedia. But make sure you have something not too taxing to soothe your brain afterwards. Another round of Overwatch, perhaps?