Richard Karp: Algorithms and Computational Complexity

Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast

Рет қаралды 140,538

Күн бұрын

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 KZfaq channel
- Twitter: / lexfridman
- LinkedIn: / lexfridman
- Facebook: / lexfridmanpage
- Instagram: / lexfridman
- Medium: / lexfridman
- Support on Patreon: / lexfridman

Пікірлер: 118

@lexfridman 3 жыл бұрын

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

@wi8shad0w 3 жыл бұрын

Thanks for this amazing series.

@nzben1993 Жыл бұрын

I’ll

@endrawes0 3 жыл бұрын

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.

@heyrmi 3 жыл бұрын

Lex many great professors are growing old each day. Geoffrey Hinton is also one of them please invite him once.

@adelmomorrison3517 3 жыл бұрын

agree!

@Sanaki131 3 жыл бұрын

@@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)

@abhishekshah11 3 жыл бұрын

As a guy who studies graph theory for purely enthusiasm, tuning into this podcast is giving me goosebumps. Thank you Lex.

@shonguiz0 3 жыл бұрын

This is a real science man, authentic talk not like some of the new age ai gurus wannabes.

@captspeedy1899 3 жыл бұрын

AGI will happen in the next 10 years. Mark my words

@shonguiz0 3 жыл бұрын

@@captspeedy1899 Maybe but i would like a better justification than the Ray Kurzweil exponential growth crap.

@joey199412 3 жыл бұрын

@@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".

@dapdizzy 3 жыл бұрын

capt speedy I know Conor McGregor used to speak like that.

@bsuperbrain 3 жыл бұрын

@@captspeedy1899 no, it won't.

@harounhajem7972 Жыл бұрын

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!

@anandbalivada7461 3 жыл бұрын

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.

@aveekbhattacharyya2550 3 жыл бұрын

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?

@KaraNodrik 3 жыл бұрын

Thank you for continually educating! I appreciate it a lot

@khuebner 3 жыл бұрын

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.

@robinampipparampil 3 жыл бұрын

This is brilliant. Complexity, networks, graphs, AI and implications for Social Psychology and Cognitive science. Thanks a lot Lex Fridman and Richard Karp.

@felixthefoxMEXICO Жыл бұрын

just saw your comment when Prof mentions this

@ronswanson3656 3 жыл бұрын

You had me at "Reducibility Among Combinatorial Problems"

@niranjanpoudel3226 11 ай бұрын

transportation problem solving are so under appreciated, mix of economics, psychology, behavior, flow ... everything

@RajeshKumar28sep 2 жыл бұрын

This video answered at least 10 questions that I always struggled with. Thanks, Lex!

@dankoni 3 жыл бұрын

once again, speaking for the devs in here, THANK YOU for episodes like this one 🙏♥️🤓

@consumer1843 3 жыл бұрын

Thank you Lex, this is a useful interview shining lights on path forward for many problems.

@SKARTHIKSELVAN 3 жыл бұрын

You ask good questions. I like your style. Thanks for your efforts.

@TravisGarnett 3 жыл бұрын

Just fascinating conversation here, especially the mentions concerning testing and human aspects!! Thank-you, gentlemen.

@bsuperbrain 3 жыл бұрын

These podcasts are amazing! Greetings from Hungary!

@timpips9115 2 жыл бұрын

Awesome Lex and Richard, thanks for simple explanations

@computersciencebyd-m-3323 Жыл бұрын

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.

@davidpolanki89 3 жыл бұрын

Thank you for the great content especially when it comes to computer science

@CryingMG 3 жыл бұрын

Richard Karp is by far one of the pillars of Computer Science, a true titan in the field. What a great podcast!

@BioCful 3 жыл бұрын

I really enjoyed listening to this program. Thanks!

@phil_781 2 жыл бұрын

xxxxxx 7

@MW_MOWGLI 3 жыл бұрын

You the man Lex, keep up the amazing work 🙌🏽

@josephwong2832 2 жыл бұрын

awesome interview. Most of those concepts are covered in competitive programmers handbook

@johangodfroid4978 3 жыл бұрын

thank you lex, excellent interview and a so my Richard karp is a so brilliant mind. Great job

@minhkhangphan9 3 жыл бұрын

Thanks for your works.

@DanyPell 2 жыл бұрын

Nice! Loving the programming podcasts.

@barisbasar3909 11 ай бұрын

How does this have so few views? Mr karp is a legend

@georgetacarmen8824 Жыл бұрын

I enjoyed this conversation. I like listening to the way that Lex's mind works. It's fascinating. :-)

@malozar9214 Ай бұрын

I suffer from severe insomnia. This helps me fall asleep. I get knocked out during the first 10min

@bunny_rabbit5753 3 жыл бұрын

I m loving this channel.🤓🤓🤓

@funkervogt47 3 жыл бұрын

"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."

@PatJHayes 3 жыл бұрын

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.

@vinca43 3 жыл бұрын

Karp.on being a.barker: "Well I wasn't particularly charming but I could be very repetitious and loud." 😂

@AIvan40 3 жыл бұрын

Maximal flow of likes > 9000

@TheMateusrex 3 жыл бұрын

Lex is doing the world a favor by interviewing the giants of computation.

@matthieucneude5761 3 жыл бұрын

Well, I finally understand P = NP problem. Thanks a lot!

@accountname1047 3 жыл бұрын

Karp's work makes me NP-hard

@callylove3637 2 жыл бұрын

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

@livinginfrance9204 3 жыл бұрын

maybe it's time for lex merch?

@NS-gr9cy 3 жыл бұрын

Do one Podcast on the new rover Perseverance going to Mars.

@JesusPirela89 Жыл бұрын

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.

@deeplearningpartnership 3 жыл бұрын

Awesome.

@LauritzMelchior 3 жыл бұрын

It good be great to invite Jim Simons.

@silencioseu 3 жыл бұрын

You should do an interview with Rich Hickey. As a fellow Lisper I think you'll appreciate him :)

@MilahanPhilosophersCorner 3 жыл бұрын

Interesting ⭐

@jjhack3r 3 жыл бұрын

Lol lex talks faster than the guest in this one. Good podcast tho

@RevenueSharePartner 3 жыл бұрын

*Algorithm: we may have not met yet, but I'm watching you (like recommendation based on what you searched)*

@mengyonglee5619 3 жыл бұрын

"I don't always sleep, but when I do I choose eightsleep", lol okay

@dapdizzy 3 жыл бұрын

This is superb advertising 😃

@dmitrym3757 2 жыл бұрын

KZfaq definitely needs a second "Like" button.

@phasm42 3 жыл бұрын

Karp's 21 NP-complete problems: en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems

@ecoyoi3015 3 жыл бұрын

Please invite professor erick demaine from MIT

@dejabu24 Жыл бұрын

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

@effoffutube 3 жыл бұрын

P=NP is perpetual motion

@johnchristopherlayton1325 3 жыл бұрын

🙏👑 #grateful

@hanes2 3 жыл бұрын

Just wanted to say, some day u should have Jonathan Blow on this podcast.

@BrianGaeddert 3 жыл бұрын

When are you going to speak to Stephanie Kelton ( The Deficit Myth )?

@seanfitzgerald4207 3 жыл бұрын

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 : )

@consumer1843 3 жыл бұрын

Do a search on the Stable Match Problem solution source code.

@socrates_the_great6209 3 жыл бұрын

Please show a drawing of what you talk about. 4:30.

@PierreH1968 3 жыл бұрын

A straight line is the shortest distance between two points, as long as the points are facing each other :))

@Paul-fn2wb 3 жыл бұрын

Sorry, I don't get it, could you explain? Or is it a joke which I don't get either? :D

@PierreH1968 3 жыл бұрын

That's the point!

@PierreH1968 3 жыл бұрын

@@Paul-fn2wb I's a corny joke and explaining it would be pointless.

@Hexanitrobenzene 3 жыл бұрын

@@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.

@yynill 3 ай бұрын

Isn't it that if you solve a NP problem it becomes a P problem by being solved. And then We have p +1

@kamilziemian995 3 жыл бұрын

Wonderful talk, truly wonderful, nonsense guest. Mister Fridman, thank you for you work.

@badwolf8112 3 жыл бұрын

CS > ALL

@annottobay Жыл бұрын

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.

@shubhamjha8896 3 жыл бұрын

Meet you in MIT Lex.

@ChurchOfThought 3 жыл бұрын

GPT-3 ....

@anjansharma5683 3 жыл бұрын

Now please invite Naval Ravikant please

@dapdizzy 3 жыл бұрын

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.

@royaebrahim2449 6 ай бұрын

❤❤

@petersmall1574 Жыл бұрын

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.

@shammcity00 3 жыл бұрын

Geoffrey Hinton pls

@toughmuon4003 3 жыл бұрын

It sounds like Mr. MagicKarp to me.

@wastingtimeofcourse3208 2 жыл бұрын

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.

@steves4069 3 жыл бұрын

Where are my shirts brother?

@a-j.2002 3 жыл бұрын

So, 2 ads every 5 minutes? Makes it hard to watch!

@snojji 3 жыл бұрын

ad block is a free browser extension that rids you of all ads on youtube

@insertoyouroemail 3 жыл бұрын

Get Simon Peyton-Jones on!

@jacobuserasmus 3 жыл бұрын

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.

@artking7883 3 жыл бұрын

@theartistbk check out canvas paintings of divine consciousness

@hanselpedia 3 жыл бұрын

Geometry problems without drawings suck! ;-)

@cridr 3 жыл бұрын

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

@geoblk3000 3 жыл бұрын

This podcast is the prime example of why there's 1.5x playback speed on KZfaq :)

@olicairns8971 3 жыл бұрын

please interview tim roughgarden

@GIBKEL 3 жыл бұрын

I lack “High dimensional intuition”....me neither. Now words have described my failure b As

@jacobuserasmus 3 жыл бұрын

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.

@jacobuserasmus 3 жыл бұрын

@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.

@Crytoma 3 жыл бұрын

@zoecadolouis578 Жыл бұрын

🇭🇹🧠👍

@bang9427 3 жыл бұрын

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?

@RevolutionOnAir84 3 жыл бұрын

@user-zj2oe5jq1u 3 жыл бұрын

Переведите на русский плиз

@sukabumiflasher4537 4 ай бұрын

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).