You are here

Algorithmic Barriers Falling: P=NP?

Front cover of 'Algorithmic Barriers Falling: P=NP?'

"A prize of $10 from Blum, $10 from Meyer, £4 from Paterson and 30-DM from Schnorr is offered to anyone who first solves the Cook-Karp problem whether P = NP.

Blum bet $100 that P ≠ NP against Paterson's $1 that P = NP."

— SIGACT News, January 1973, page 3.

These playful bets capture youthful optimism in Complexity Theory. Did Donald E. Knuth share this optimism at the time? And how did the findings of complexity theorists interlace with Knuth's pioneering work in the Analysis of Algorithms?

By investigating Knuth's developing thoughts on the theoretical underpinnings of efficient computation, this book sheds light on Knuth's present-day conjecture that P = NP.

Book details

Conversations issue 4
Algorithmic Barriers Falling: P=NP?
A conversation with Donald E. Knuth conducted by Edgar G. Daylight
Edited by K. De Grave
Paperback, 116+i pages
Published November 2014
ISBN 978-94-9138-604-6
Conversations ISSN 2034-5976

Available at,,,, etc (Worldwide), (US), Alibris (US/UK), Bookdepository (Worldwide), BOL (DE, NL, BE), and many other bookstores worldwide. If it's not in stock at your favorite bookstore, ask the shopkeeper to order from Ingram (US), Bertrams (UK), or Gardners (UK).