newsfilter
← Interviews
Lex Fridman11 min

Donald Knuth: P=NP | AI Podcast Clips

Donald Knuth, Lex Fridman

Interview

The speaker argues that mathematical existence proofs for algorithms, such as those in the Hex game and the Robertson-Seymour theorem, often reveal solutions that are provable yet practically undiscoverable due to human comprehension limits. Based on the vast scale of the algorithmic search space, the speaker intuitively posits that P equals NP, asserting that polynomial-time solutions for NP problems likely exist by chance even if no human has ever constructed them. This stance rejects the absence of evidence as proof of non-existence, comparing the search for efficient algorithms to the search for extraterrestrial life where the sheer number of possibilities makes finding a solution plausible.