? DoesP=NP. In just ?ve symbols Dick Karp -in 1972-captured one of the
deepest and most important questions of all time. When he ?rst wrote his
famous paper, I think it's fair to say he did not know the depth and
importance of his question. Now over three decades later, we know P=NP
is central to our understanding of compu- tion, it is a very hard
problem, and its resolution will have potentially tremendous
consequences. This book is a collection of some of the most popular
posts from my blog-- Godel ] Lost Letter andP=NP--which I started in
early 2009. The main thrust of the blog, especially when I started, was
to explore various aspects of computational complexity around the
famousP=NP question. As I published posts I branched out and covered
additional material, sometimes a timely event, sometimes a fun idea,
sometimes a new result, and sometimes an old result. I have always tried
to make the posts readable by a wide audience, and I believe I have
succeeded in doing this.