Skip to content
Hallway
0:00 / 0:00

#donaldknuth#pvsnp#complexitytheory

Donald Knuth: P=NP | AI Podcast Clips

Lex Fridman

5M subscribers • 39 videos on Hallway

YouTube
  • Recommended by 3 people: 3 in engineering communities.
  • A classic. People kept recommending it from 2020 to 2025.
  • Presented by Donald Knuth, computer scientist
  • An opinion. It argues one side of a question engineers disagree on.

Advanced. Deep dive for people who know the field.

70K views6 years ago3 recommendations

Computer scienceComputation and complexityAlgorithms

Donald Knuth discusses his perspective on the P versus NP problem and why he believes P might equal NP.

Full episode with Donald Knuth (Dec 2019): youtube.com/watch?v=2BdBfsXbST8 Clips channel (Lex Clips): youtube.com/lexclips Main channel (Lex Fridman): youtube.com/lexfridman (more links below) Podcast full episodes playlist: youtube.com/playlist?list=PLrAXtmErZgOdP_8GztsuKi9nrraNbKKp4 Podcasts clips playlist: youtube.com/playlist?list=PLrAXtmErZgOeciFP3CBCIEElOJeitOr41 Podcast website: lexfridman.com/ai Podcast on Apple Podcasts (iTunes): apple.co/2lwqZIr Podcast on Spotify: open.spotify.com/show/2MAi0BvDc6GTFvKFPXnkCL Podcast RSS: lexfridman.com/category/ai/feed/ Donald Knuth is one of the greatest and most impactful computer scientists and mathematicians ever. He is the recipient in 1974 of the Turing Award, considered the Nobel Prize of computing. He is the author of the multi-volume work, the magnum opus, The Art of Computer Programming. He made several key contributions to the rigorous analysis of the computational complexity of algorithms. He popularized asymptotic notation, that we all affectionately know as the big-O notation. He also created the TeX typesetting which most computer scientists, physicists, mathematicians, and scientists and engineers use to write technical papers and make them look beautiful. Subscribe to this YouTube channel or connect on: - Twitter: twitter.com/lexfridman - LinkedIn: linkedin.com/in/lexfridman - Facebook: facebook.com/lexfridman - Instagram: instagram.com/lexfridman - Medium: medium.com/@lexfridman - Support on Patreon: patreon.com/lexfridman

Why it's here

3 people recommend this

What people say. Engineers point to this for Knuth's interesting insight that P could equal NP without practical real-world consequences.

u/6u2m4n79in r/compsci • Recommends

On “If P=NP, what would mean for non-researchers and academic folks? How would change, if any at all, the way we write softwares?”

Lex Friedman Podcast with Donald Knuth. P=NP? link to this video
7View on Reddit

u/miki151in r/compsci • Recommends

On “The P = NP Problem”

Here is a very interesting insight on this by Donald Knuth link to this video He makes a point that it's possible that P can be equal to NP without any real-world consequences, like invalidating current public key cryptography.
3View on Reddit

u/brightpixelsin r/compsci • Recommends

On “I dedicated three years to work on Travelling Salesman Problem.”

Yeah. TLDR he believes that the algorithms are probably out there but inaccessible to the human mind. link to this video
3View on Reddit