Home » Uncategorized » Is It New?

Is It New?

Gödel's Lost Letter and P=NP

egdaylightSummerPic

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.

Knuthbook

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

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: