Josh Davis

I'm currently an Engineer working on machine learning at AWS and am living in Seattle.

I like to learn, pet kittens, and wear fluffy socks.

I never save anything for the swim back.

07 July 2013

Verification is Often Easier than Creation

This past Spring semester (Spring 2013), I took the best Computer Science class (at least so far) that I’ve taken at University. The class was called “Theory of Computing” and was taught by Ting Zhang.

The textbook that we used was the classic Michael Sipser book, Introduction to the Theory of Computation. I ended up absolutely loving the class so I asked my professor for a recommendation for further reading on the subject. He recommended Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. I’ve finally found a chance to dig into it this summer and I came across a quote that struck me because it was a notion that I hadn’t given much thought to.

Here’s the quote (emphasis mine):

… the P versus NP question captures a widespread phenomenon of some philosophical importance (and a source of great frustration): recognizing the correctness of an answer is often much easier than coming up with the answer. Appreciating a Beethoven sonata is far easier than composing the sonata; verifying the solidity of a design for a suspension bridge is easier (to a civil engineer anyway!) than coming up with a good design; verifying the proof of a theorem is easier than coming up with a proof itself (a fact referred to in Godel’s letter quoted at the start of the chapter), and so forth.

The idea that struck me was that the implications of the P vs NP problem goes beyond mathematics into fields such as art and engineering.

There’s no way I could even count the number of times I’ve seen a great user interface that works intuitively and well (verification) and have struggled to design something for a similar project that I’m working on (creation).

It’s very easy to be using a service such as Google Maps, buying something off of Amazon, or even just looking at my Twitter feed and seeing and verifying that it works well but not being able to fathom how much time it took to create such a service.

In a way, it is a very strong reminder that some great things take time. There’s no way to fake that. While it is possible to create great things in a short amount of time, some things might only take hard work and persistence.

You're awesome for reading this. You should follow me on Twitter and GitHub.