Video Review: Vinay and Maru Prove that P ≠ NP

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.

In Episode 2, Deolalikar talks about problems that involve finding a set of true-or-false values that solve a particular type of expression, while Maru uses wooden blocks (oriented vertically for “true” and horizontally for “false”) to demonstrate trying different value combinations. Unfortunately, Episode 2 doesn’t quite live up to the promise of Episode 1 — as much as it pains me to say this, I think Maru’s performance is lacking in this episode. We never actually see the expression he’s trying to solve, and at times it almost seems as if he’s just playing with the blocks.

Solutions to the type of problem defined in Episode 2 are easy to verify. In Episodes 3-7, Deolalikar proves that some problems of that type are difficult to solve, while Maru has a series of math-themed adventures.

Episode 8 features an interactive Q&A session with Deolalikar and an interactive play session with Maru.

The series concludes with an epilogue in which Deolalikar discusses the experience of researching, formulating, and writing his proof while Maru approaches a task with single-minded focus. To avoid giving away the ending, they’ve produced two alternate versions of the epilogue: one assumes the proof is valid; the other assumes it is fatally flawed.

Overall, I’d give this series 4 stars out of 5. If you liked Andy and Maru Prove Fermat’s Last Theorem, you’ll love this.

2 thoughts on “Video Review: Vinay and Maru Prove that P ≠ NP

Leave a comment. Please.

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.