#111 – Richard Karp: Algorithms and Computational Complexity

Lex Fridman Podcast

Lex Fridman

Philosophy, Society & Culture, Science, Technology

4.7 • 13K Ratings

🗓️ 26 July 2020

⏱️ 128 minutes

🔗️ Recording | iTunes | RSS

🧾️ Download transcript

Summary

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

Transcript

Click on a timestamp to play from that location

0:00.0	The following is a conversation with Richard Carp, a professor at Berkeley,
0:04.2	and one of the most important figures in the history of theoretical computer science.
0:09.4	In 1985, he received the Turing Award for his research in the theory of algorithms,
0:15.0	including the development of the admins Carp algorithm for solving the max flow problem on
0:20.6	networks, hop-crawf-carp algorithm for finding maximum cardinality, matchings, and bipartite graphs,
0:27.9	and his landmark paper and complexity theory called reducibility among combinatorial problems,
0:35.1	in which he proved 21 problems to be NP-complete. This paper was probably the most important
0:41.1	catalyst in the explosion of interest in the study of NP-completeness and the P versus NP problem in
0:47.9	general. Quick summary of the ads, two sponsors, A Sleep mattress and cash app. Please consider
0:54.0	supporting this podcast by going to aesleep.com slash Lex and downloading cash app and using
1:00.9	code Lex Podcast. Click the links by the stuff it really is the best way to support this podcast.
1:07.8	If you enjoy this thing, subscribe on YouTube, review it with 5 stars and not per podcast,
1:12.3	supporting on Patreon, or connect with me on Twitter at Lex Friedman. As usual, I'll do a
1:17.6	few minutes of ads now and never any ads in the middle that can break the flow of the conversation.
1:22.8	This show is sponsored by A Sleep and it's pod pro mattress that you can check out at aesleep.com
1:29.5	slash Lex to get $200 off. It controls temperature with an app. It can cool down to as low as 55
1:37.7	degrees and each side of the bed separately. Research shows the temperature has a big impact on
1:43.5	the quality of our sleep and, in totally, it's been a game changer for me. I love it. It's been a
1:49.1	couple of weeks now. I've just been really enjoying it, both in the fact that I'm getting better
1:53.8	sleep and then it's a smart mattress. Essentially, I kind of imagine it's being the early days of
2:00.5	artificial intelligence being a part of every aspect of our lives and certainly,
2:04.9	infusing AI in one of the most important aspects of life, which is sleep, I think, has a lot of
	...

Please login to see the full transcript.

Previous episode | Next episode

Disclaimer: The podcast and artwork embedded on this page are from Lex Fridman, and are the property of its owner and not affiliated with or endorsed by Tapesearch.

Generated transcripts are the property of Lex Fridman and are distributed freely under the Fair Use doctrine. Transcripts generated by Tapesearch are not guaranteed to be accurate.