Title: Algorithmic Barriers Falling: P=NP?
Authors: Knuth, Donald E.
Daylight, Edgar G.
Editors: De Grave, Kurt
Issue Date: 2014
Publisher: Lonely Scholar
Series Title: Conversations vol:2014
Abstract: "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.
ISBN: 978-94-9138-604-6
ISSN: 2034-5976
Publication status: published
KU Leuven publication type: IBe
Appears in Collections:Informatics Section

Files in This Item:
File Description Status SizeFormat
KnuthParis24.pdfbookblock Published 512KbAdobe PDFView/Open

These files are only available to some KU Leuven Association staff members


All items in Lirias are protected by copyright, with all rights reserved.