Month: October 2017

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

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.

“Worry if the new generation is less familiar with technology internals than we were”

I’ve posted this in 2014, but a friend’s comment on facebook makes me want to repost this:

“I think we’ve had a reduction from, say, if you think about 1995, which was when I went to college, you could typically rely on an undergraduate having done a substantial amount of real programming, often quite a deep level of technical work on one or more platforms. Many of us could program in one or more assembly languages. And yeah, within 10 years of that point, we were getting to a point where your average applicant was maybe somebody who’d done, as you say, a little bit of Web design, maybe a little bit of Web programming—you know, we saw quite a bit of people who‘d maybe done some PHP but not that kind of deep technical understanding of how machines work.”

This was from an Eben Upton interview. So much progress has happened that people entering the profession do so with a distance from the hardware.