#111 – Richard Karp: Algorithms and Computational Complexity

Jul 26, 2020

Richard Karp, a professor at Berkeley and a Turing Award recipient, dives deep into the world of algorithms and computational complexity. He shares insights on the beauty of geometric reasoning and its impact on algorithm design. Karp discusses the elusive P vs NP problem, reflecting on its significance in theoretical computer science. He also explores the connection between algorithms and human emotions, alongside the fascinating implications of randomization in problem-solving. Anecdotes from his teaching experiences highlight the joy of educating future minds in this complex field.

Ask episode

AI Snips

Chapters

Transcript

Episode notes

ANECDOTE

Shortest Distance between Circles

Richard Karp recounts a story about Michael Rabin finding the shortest distance between two non-overlapping circles.
Rabin's elegant solution impressed young Karp with the power of pure reasoning.

INSIGHT

Elegance of Geometric Proofs

Karp finds elegance in proving facts through pure reasoning, like the sum of angles in a triangle.
This contrasts with earlier math courses focused on arithmetic manipulation, offering a new level of certainty.

ANECDOTE

Discovering the "Geek" Identity

Richard Karp discovered his "geek" identity when learning the Hungarian algorithm for the assignment problem.
This algorithm's systematic approach resonated with him, similar to the satisfaction of shaping materials in woodworking.

Get the Snipd Podcast app to discover more snips from this episode

Get the app

Richard Karp is a professor at Berkeley and one of the most important figures in the history of theoretical computer science. In 1985, he received the Turing Award for his research in the theory of algorithms, including the development of the Edmonds–Karp algorithm for solving the maximum flow problem on networks, Hopcroft–Karp algorithm for finding maximum cardinality matchings in bipartite graphs, and his landmark paper in complexity theory called “Reducibility Among Combinatorial Problems”, in which he proved 21 problems to be NP-complete. This paper was probably the most important catalyst in the explosion of interest in the study of NP-completeness and the P vs NP problem.

Support this podcast by supporting our sponsors:
– Eight Sleep: https://eightsleep.com/lex
– Cash App – use code “LexPodcast” and download:
– Cash App (App Store): https://apple.co/2sPrUHe
– Cash App (Google Play): https://bit.ly/2MlvP5w

If you would like to get more information about this podcast go to https://lexfridman.com/ai or connect with @lexfridman on Twitter, LinkedIn, Facebook, Medium, or YouTube where you can watch the video versions of these conversations. If you enjoy the podcast, please rate it 5 stars on Apple Podcasts, follow on Spotify, or support it on Patreon.

Here’s the outline of the episode. On some podcast players you should be able to click the timestamp to jump to that time.

OUTLINE:
00:00 – Introduction
03:50 – Geometry
09:46 – Visualizing an algorithm
13:00 – A beautiful algorithm
18:06 – Don Knuth and geeks
22:06 – Early days of computers
25:53 – Turing Test
30:05 – Consciousness
33:22 – Combinatorial algorithms
37:42 – Edmonds-Karp algorithm
40:22 – Algorithmic complexity
50:25 – P=NP
54:25 – NP-Complete problems
1:10:29 – Proving P=NP
1:12:57 – Stable marriage problem
1:20:32 – Randomized algorithms
1:33:23 – Can a hard problem be easy in practice?
1:43:57 – Open problems in theoretical computer science
1:46:21 – A strange idea in complexity theory
1:50:49 – Machine learning
1:56:26 – Bioinformatics
2:00:37 – Memory of Richard’s father