Today is the official publication date of my first book The Golden Ticket: P, NP and the Search for the Impossible by Princeton University Press, though the book has been available on Amazon and in some bookstores for a couple of weeks now. This book takes a non-technical tour of our favorite open question through a series of stories and examples, covering P, NP, NP-complete, the "beautiful world" if P = NP, and how to deal with hard problems since we surely don't live in that world and a bit of history, cryptography and quantum. How "non-technical": I never actually define P and NP and avoid formulas and terminology except as needed to describe circuits and Cook's theorem.I spent three years on this book project, building on my CACM survey. Thanks to all of you readers for your support, your suggestions for maps (some of which I used), titles and epigraphs (none of which I used).
You can keep up with all the happenings of the book on its own twitter and website.The Golden Ticket has already received some nice reviews. You can also check out an article I wrote for the Daily Dot and podcasts interview at Wild About Math and the New Books Network. There are Japanese and Chinese translations in the works.
Hope you enjoy the book, recommend it all all your friends and help preach the gospel of P v NP.
Congrats Lance! Writing a book is a lot of work.
ReplyDeleteI was just telling a friend that we need more books like this, an introduction to this problem for people who don't want to have to go through papers on automata, languages, reducability and Turing machines first. I'll definitely check it out.
ReplyDeleteCongratulations, Lance
ReplyDeleteIndeed the P NP story is an amazing story of our time
My personal copy of the book has just arrived, and my institute's library copy is on the way. Looking forward to reading it, and even more, offering it to non-cs, non-science, non-academia friends who wonder what kind of work I do. I feel I've never been able to satisfactorily describe the story and the excitement. Lance, thanks for writing it!
ReplyDeleteStudents especially should be aware that Lance's The Golden Ticket provides an in-depth exposition of Lance's Communications of the ACM survey "The status of the P versus NP problem" (2009). The Golden Ticket provides a wonderful book-length exposition of the ideas, the history, and the research community behind this outstanding article.
ReplyDeleteWhy if P=NP is public key crypto impossible? As long as there are any complexity amplification between checking and searching (it doesn't have to be an exponential gap), there is possibility of PKC, albeit with the need of extremely long keys?
ReplyDelete