P vs. NP is one of the most famous unsolved problems in math. Recently, mathematician Vinay Deolalikar circulated a paper that contained a possible solution to that problem. There’s been lots of discussion on the Internet about this paper; surprisingly, though, the companion video series has been largely ignored.

In Vinay and Maru Prove that P ≠ NP, Deolalikar presents the material from his paper with the assistance of Maru, who is possibly the most entertaining cat on YouTube. Each episode features video imagery of Maru with narration by Deolalikar. In Episode 1, Deolalikar defines what P ≠ NP means — basically, that the solutions to some problems are hard to find but easy to verify — while Maru interacts with a large cardboard box. Finding a way into the box is a difficult problem for Maru; eventually, he solves it and goes on to demonstrate (repeatedly) that verifying the solution is easy. Of course, the fact that Maru found the initial problem difficult doesn’t prove anything; it’s possible that someone could discover a simpler box-entry-finding algorithm tomorrow. Episode 1 gets two thumbs up from me — the narration is clear and informative, and Maru’s performance is outstanding.
Continue reading “Video Review: Vinay and Maru Prove that P ≠ NP” →