Home

The Golden Ticket: P, NP, and the Search for the Impossible

2017/10/14

As long as P versus NP remains a mystery we do not know what we cannot do, and that’s liberating.

I follow Lance Fortnow’s blog from time to time. So when the book was out, I fired up the kindle and bought it. And then it stayed there for some time. Most likely because two out of seven days of the week I am not sure I can explain P vs NP. The rest I might be able, but the difficulty of the problem makes one double think about it, even when it is a book that makes it accessible to the general public. After all, it is The Problem.

And then came a plane trip. And with nowhere to go for the next 2,5 hours I started reading it. Fast. The history of the problem is there. Examples that are very easily understood are there. The hop from the example to the equivalent real problem is there, so you get to understand vertex cover before ever knowing the name.  Plus you get to learn a bit about complexity during the Cold War and about quantum computing too.

We know for example that if P=NP, then cryptography as we know it will be defeated. But how will other aspects of our World change? Fortnow offers a glimpse. Is it worth it? Maybe. You will be the judge. Is it likely that P=NP? The author does not believe so (I do not want it to be, and want versus believe denotes the vast skill difference between him and me).

Chapter 2 was a bit boring for me and I almost gave up on the book. Fortunately I did not. If you are a computational complexity theorist then the book is not for you, but if you are not and you want to ask clear questions to one, then it will definitely help.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

%d bloggers like this: