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.

Tagged with: , , , , , , ,
Posted in Cats, Humor, Math
2 comments on “Video Review: Vinay and Maru Prove that P ≠ NP
  1. *giggles* And Laura, you must be a genius! You have found a way for be to read about math without getting a giant migraine! :-)

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Elsewhere …

I have some publications in other places, including short stories at Shimmer, Flash Fiction Online, and Daily Science Fiction, and a list of overly-wordy LOLCat captions on McSweeney's.

Things I found in my cat's water bowl.

A blog about my cat Holly's end of life.

Follow Unlikely Explanations on

Enter your email address to follow this blog and receive notifications of new posts by email.

Less Recent Posts
The Archives page has links to every post that's ever appeared on this blog.
Not what you were looking for?
If a search engine brought you here while you were looking for something else, please see An Open Letter to Anyone Who Was Directed Here by a Search Engine.
Unlikely Tweets
Freshly Pegged
%d bloggers like this: