Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast
ฝัง
- เผยแพร่เมื่อ 5 ก.ค. 2024
- Richard Karp is a professor at Berkeley and one of the key 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 signing up with these sponsors:
- Eight Sleep: eightsleep.com/lex
- Cash App - use code "LexPodcast" and download:
- Cash App (App Store): apple.co/2sPrUHe
- Cash App (Google Play): bit.ly/2MlvP5w
EPISODE LINKS:
Richard's wikipedia: en.wikipedia.org/wiki/Richard...
PODCAST INFO:
Podcast website:
lexfridman.com/podcast
Apple Podcasts:
apple.co/2lwqZIr
Spotify:
spoti.fi/2nEwCF8
RSS:
lexfridman.com/feed/podcast/
Full episodes playlist:
• Lex Fridman Podcast
Clips playlist:
• Lex Fridman Podcast Clips
OUTLINE:
0:00 - Introduction
3:50 - Geometry
9: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
CONNECT:
- Subscribe to this TH-cam channel
- Twitter: / lexfridman
- LinkedIn: / lexfridman
- Facebook: / lexfridmanpage
- Instagram: / lexfridman
- Medium: / lexfridman
- Support on Patreon: / lexfridman - วิทยาศาสตร์และเทคโนโลยี
I really enjoyed this conversation with Richard. Here's the outline:
0:00 - Introduction
3:50 - Geometry
9: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
Thanks for this amazing series.
I’ll
Whenever an older person is in the show I know I'm in for a treat of wisdom. Especially love it when it's computer science related.
As a guy who studies graph theory for purely enthusiasm, tuning into this podcast is giving me goosebumps. Thank you Lex.
Lex many great professors are growing old each day. Geoffrey Hinton is also one of them please invite him once.
agree!
@@kiran0511 you can do podcasts standing up :> Hinton and Jeff Dean would be amazing, but I'm guessing they have very little time (and don't seem to be very interested in doing public appearences outside of Google)
This is a real science man, authentic talk not like some of the new age ai gurus wannabes.
AGI will happen in the next 10 years. Mark my words
@@captspeedy1899 Maybe but i would like a better justification than the Ray Kurzweil exponential growth crap.
@@captspeedy1899 Based on what? Your gut feeling? At least provide some scientific basis for your assertion. Link some sources etc.
saying "X will happen in Y years, mark my words" without anything to back it up is the same as a homeless person holding up a sign saying "The end is nigh".
capt speedy I know Conor McGregor used to speak like that.
@@captspeedy1899 no, it won't.
You know when it's a very intelligent person talking when that person can take really complex tasks and break them down and explain them to anyone. Thanks for the podcast Lex Friedman and Richard Karp!
I have been waiting for this for so long :))). I attended a public lecture by Richard Karp and was in awe the entire time and absolutely loved it. He was so excited, sharp and passionate even at 84 and I derived a better understanding of the nature of problems in theoretical cs and the structure of the field in general.
Hey Lex your podcast is just like the e^x graph which keeps on increasing in the positive direction of the x axis. They are literally amazing. Can you bring Linus Torvalds next?
This is brilliant. Complexity, networks, graphs, AI and implications for Social Psychology and Cognitive science. Thanks a lot Lex Fridman and Richard Karp.
just saw your comment when Prof mentions this
Thank you for continually educating! I appreciate it a lot
You had me at "Reducibility Among Combinatorial Problems"
Thank you Lex for providing an outline to your video! Makes it easy to listen to areas of interest. I wish more video bloggers would do this.
transportation problem solving are so under appreciated, mix of economics, psychology, behavior, flow ... everything
This video answered at least 10 questions that I always struggled with. Thanks, Lex!
once again, speaking for the devs in here, THANK YOU for episodes like this one 🙏♥️🤓
Richard Karp is by far one of the pillars of Computer Science, a true titan in the field. What a great podcast!
Thank you very much for this interview with Prof. Karp. For me, computational complexity is the most fascinating topic, and it is absolutely great to hear the major contributors talk about it.
Just fascinating conversation here, especially the mentions concerning testing and human aspects!! Thank-you, gentlemen.
These podcasts are amazing! Greetings from Hungary!
Thank you Lex, this is a useful interview shining lights on path forward for many problems.
You ask good questions. I like your style. Thanks for your efforts.
Thank you for the great content especially when it comes to computer science
You the man Lex, keep up the amazing work 🙌🏽
Awesome Lex and Richard, thanks for simple explanations
awesome interview. Most of those concepts are covered in competitive programmers handbook
I really enjoyed listening to this program. Thanks!
xxxxxx 7
Karp.on being a.barker: "Well I wasn't particularly charming but I could be very repetitious and loud." 😂
I enjoyed this conversation.
I like listening to the way that Lex's mind works.
It's fascinating.
:-)
"If an elderly but distinguished scientist says that something is possible, he is almost certainly right; but if he says that it is impossible, he is very probably wrong."
Years ago I was the plenary speaker at a AAAI Spring symposium. I summed it up by saying that the talks consisted of old men explaining why various things were impossible interspersed with young men explaining how they had just implemented them.
thank you lex, excellent interview and a so my Richard karp is a so brilliant mind. Great job
Maximal flow of likes > 9000
Nice! Loving the programming podcasts.
Thanks for your works.
I suffer from severe insomnia. This helps me fall asleep. I get knocked out during the first 10min
How does this have so few views? Mr karp is a legend
I believe that the constrained version of the stable marriage problem Karp is explaining at around 1:18:00 is about the difference between matching a pair and a triple. Pair matching is a problem in P while triple matching is an NP-complete problem
Lex is doing the world a favor by interviewing the giants of computation.
I m loving this channel.🤓🤓🤓
Karp's work makes me NP-hard
Do one Podcast on the new rover Perseverance going to Mars.
Well, I finally understand P = NP problem. Thanks a lot!
I think it would be interesting to see an episode with Richard Garfield talking about AI, Mathematics and Magic the Gatering, I think it would be a good programme.
You should do an interview with Rich Hickey. As a fellow Lisper I think you'll appreciate him :)
maybe it's time for lex merch?
*Algorithm: we may have not met yet, but I'm watching you (like recommendation based on what you searched)*
"I don't always sleep, but when I do I choose eightsleep", lol okay
This is superb advertising 😃
Very interesting, I used to hate math when I was in school but only because I found it useless and boring , learning by myself allowed me to see the beauty and power of mathematics and is fascinating
Lol lex talks faster than the guest in this one. Good podcast tho
It good be great to invite Jim Simons.
Most rational and humbling opinion about AI I have gotten from a Mathematician/Computer Scientist. Unlike, some I am not even remotely fearful of AI. It maybe blissful ignorance, however, I have absolutely no fear of a machine becoming sentient and be able to compete on a human level with even the most uneducated and low IQ among the human population. AI will never be able to reproduce itself or have the range of human emotions or self-awareness as human beings. Even the lowest IQ among us have a human spirit about them along with the capacity to produce off springs that can differ from themselves in ability, ambition, outlook, and approach to life. This produces a diversity of creativity, approach to life and ambition that is more than raw ability to engage in infinite computation in an extremely efficient manner.
Please invite professor erick demaine from MIT
Interesting ⭐
When are you going to speak to Stephanie Kelton ( The Deficit Myth )?
P=NP is perpetual motion
Karp's 21 NP-complete problems: en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems
stable marriage problem is central to the matching algorithm i need to create for my DeepMatch (candidate/company matching) startup. if anyone listening out there has algorithm development expertise and is interested in potentially working with me on this, please reach out : )
Do a search on the Stable Match Problem solution source code.
Awesome.
Just wanted to say, some day u should have Jonathan Blow on this podcast.
Please show a drawing of what you talk about. 4:30.
Isn't it that if you solve a NP problem it becomes a P problem by being solved.
And then We have p +1
TH-cam definitely needs a second "Like" button.
A straight line is the shortest distance between two points, as long as the points are facing each other :))
Sorry, I don't get it, could you explain? Or is it a joke which I don't get either? :D
That's the point!
@@Paul-fn2wb I's a corny joke and explaining it would be pointless.
@@Paul-fn2wb
I suspect it's a sentence similar in spirit to the one I encountered in a science encyclopedia text about topology: "Please lay the tablecloth with a hole facing upwards."
Points, as well as holes, simply don't have direction property.
Wonderful talk, truly wonderful, nonsense guest. Mister Fridman, thank you for you work.
Upon hearing "Hungarian Algorithm", my mind leapt to "Bohemian Rhapsody." Then, when I heard him describe the Assignment Problem, it occurred to me that the search for a solution to this problem through the application of a computational algorithm is exactly the kind of challenge that would appeal to geeky young men desperate to discern how they could identify girls who might be willing to go out on a date with them.
This guys explanation on why he is doubtful on AI just doesn’t justify reality. Tech will continue to improve dramatically. Maybe AI won’t exist in his lifetime, but humanity will definitely achieve it.
I like how Alex seems to completely miss the first two beautiful examples that the guest presents to him, yet he is perfectly polite and the conversation goes as if there is a perfect understanding between the two.
GPT-3 ....
Now please invite Naval Ravikant please
So, 2 ads every 5 minutes? Makes it hard to watch!
ad block is a free browser extension that rids you of all ads on youtube
CS > ALL
Where are my shirts brother?
🙏👑 #grateful
Meet you in MIT Lex.
being from eastern europe, when you say Lex Fridman withouth the "i"( how you hear, not how you write it) it was strange to understand what do you mean .. I always forget this strange thing in english when they say "i" and they refer to "e" and when they say "ei" and the refer to "a" or "i" ?! hopefully a AGI will find this strange too
I think it is really important to understand machines do not have to have Artificial General Intelligence for AI to be a thread to our existence, nor do they need self consciousness. An AI with mastery of a very small domain and enough control can effectively end the human race. (Eg. Military Strategy) The problem with AGI is just much worse and the way I see it is that the moment AGI exist it will be impossible to stop it.
Geoffrey Hinton pls
@theartistbk check out canvas paintings of divine consciousness
I of course think AGI is inevitable, Single Cell organism builds Multi Cellular organism eventually builds a brain, which eventually evolve into Self Consciousness which eventually evolve into Super Consciousness. I thin AGI is just part of natural evolution.
@FeatherFiend jip. Blows the mind. But I think that a lot of people do not realize that we are already part of a bigger organism. It's even in the name Organization, it even has legal standing. It has specialization of components, communication between components, will to survive, natural selection. This goes for both companies and countries.The question to ask is AGI the evolution of a organization (business) or the evolution of a country or the evolution of a human being. I personally think it is just the evolution of a organization.
It sounds like Mr. MagicKarp to me.
Get Simon Peyton-Jones on!
Geometry problems without drawings suck! ;-)
❤❤
I lack “High dimensional intuition”....me neither. Now words have described my failure b
As
This podcast is the prime example of why there's 1.5x playback speed on TH-cam :)
please interview tim roughgarden
i usually enjoy the podcast, but this time the questions could be answered by a bachelor student in CS very easily. I think it was a waste of Richard Karp. Maybe making a voting system?
++
p is not the same as np so this is true if we use binary logic 1 (true) & 0 (false).
p is the same as np so this is true if we use antilogic/quantum logic 1=0 (true = false).
🇭🇹🧠👍
Переведите на русский плиз
.
So this must all mean the world is definitely flat then?
stable marriage problem = cuckoo hashing, surprisingly
Whenever an older person is in the show I know I'm in for a treat of wisdom. Especially love it when it's computer science related.
++
++