Pink Iguana

Home » Uncategorized » Is It New?

Is It New?


Gödel's Lost Letter and P=NP


Edgar Daylight was trained both as a computer scientist and as a historian. He writes a historical blog themed for his near-namesake Edsger Dijkstra, titled, “Dijkstra’s Rallying Cry for Generalization.” He is a co-author with Don Knuth of the 2014 book: Algorithmic Barriers Failing: P=NP?, which consists of a series of interviews of Knuth, extending their first book in 2013.

Today I wish to talk about this book, focusing on one aspect.

The book is essentially a conversation between Knuth and Daylight that ranges over Knuth’s many contributions and his many insights.


One of the most revealing discussions, in my opinion, is Knuth’s discussion of his view of asymptotic analysis. Let’s turn and look at that next.

Asymptotic Analysis

We all know what asymptotic analysis is: Given an algorithm, determine how many operations the algorithm uses in worst case. For example, the nave matrix product of square $latex {n}&fg=000000$…

View original post 596 more words


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: