30초 요약
In this clip, Donald Knuth tells Lex Fridman that he suspects P equals NP, but that a proof would not hand us useful algorithms. He points to the game of Hex and the Robertson–Seymour graph minor theorem as cases where algorithms provably exist yet remain unknown. His intuition rests on the sheer number of possible algorithms, though he stresses it is no proof.
- 1An algorithm can exist without anyone knowing itKnuth argues that the total number of algorithms is mind-boggling, and most are far beyond human comprehension, so a proof of P = NP would not directly yield a practical method.
- 2Hex shows existence without constructionThe game cannot end in a draw, so one of the two players must have a winning strategy, yet nobody knows an algorithm for finding it.
- 3The Robertson–Seymour theorem guarantees polynomial-time algorithms we cannot writeAny class of graphs closed under minors is characterized by a finite list of forbidden minors, but we may not know that list.
- 4The intuition for P = NP comes from the size of the search spaceWith so many possible algorithms, Knuth says, surprising coincidences are to be expected, much like two people sharing the same number of hairs.
- 5Failure to find an algorithm is weak evidenceKnuth notes that the same logic could be flipped, since many smart people have also failed to prove P is unequal to NP.
챕터별 전체 원고 읽기
A proof that an algorithm exists is not an algorithm
Fridman opens by recalling that Donald Knuth has said he believes P may equal NP, while also arguing that such a proof would not directly lead to algorithms for hard problems. Knuth explains that the popular assumption is that if an algorithm exists, somebody will eventually find it. He says that is wrong: many more algorithms exist than anyone can ever understand or discover, because they are way beyond human comprehension.
To make the point concrete, Knuth turns to the game of Hex, played by placing pebbles on a hexagonal board. One player tries to connect left to right and the other bottom to top, there is no capture, and, crucially, there are no draws. Because it is a finite game of perfect information, one of the two players must have a winning strategy.
Knuth says you can even show that it has to be one or the other, using an argument about the second player mimicking the first. Yet this tells us nothing about which player wins or how to play. In his words, we know the algorithm exists but have no idea what it is.
Graph minors give polynomial algorithms nobody can write down
Knuth's second example is the Robertson–Seymour theorem from graph theory. It says that every class of graphs closed under taking minors has a polynomial-time membership test. Planar graphs are the standard example: shrinking an edge to a point or deleting an edge leaves a planar graph planar. Knuth says the proof spans a sequence of some twenty papers and is deep work.
The key result is that any such family has a finite number of minimal forbidden graphs. For planar graphs there are two, the five-pointed star in which everything connects to everything and the three-utilities-to-three-houses graph. Any non-planar graph can be shrunk down until it contains one of these two bad graphs. Knuth notes that the theorem applies to any arbitrary minor-closed class, and that many important classes arising in applications have this property.
Knuth then walks through why this gives a polynomial algorithm. You test whether the input graph contains each bad minor, each test takes polynomial time, and there are only finitely many tests. The catch is that for an arbitrary class we only know the list is finite. We might know one or two of the forbidden minors while there could be 125 more, so we hold a polynomial-time algorithm that we cannot actually write.
Why Knuth still leans toward P = NP, though not by proof
Fridman asks why Knuth holds the intuition that P equals NP at all. Knuth answers that to believe otherwise you would have to rule out an enormous number of possible algorithms. He gives an example of an odd but perfectly valid polynomial-time procedure, such as encoding a graph with prime numbers and combining them with bitwise operations. There are so many algorithms of this kind that some random-looking one may well happen to solve a problem.
He compares this to coincidences in everyday counting. It seems unlikely that two people have the same number of hairs on their heads, but given how many people there are, such pairs must exist. Likewise, when the space of possibilities is huge, a particular combination of operations might just happen to prove that a graph has a Hamiltonian path. Knuth emphasizes that this is by no means a proof.
He also rejects the opposite argument that P cannot equal NP because brilliant people and million-dollar prizes have not produced an algorithm. By the same logic, he says, one could argue P must equal NP because so many smart people have tried and failed to prove otherwise. Fridman likens it to the search for aliens, and Knuth agrees that the number of planets makes their existence plausible, even if they have not been found.
같은 채널의 다른 글
3:36:56EN
Lex Fridman· 2026년 9월 16일팟캐스트Psychiatry Has Never Found Its Penicillin진행자 Lex FridmanHistorian Andrew Scull tells Lex Fridman why the field can ease symptoms, has never cured a major mental illness, and keeps paying for overconfidence with patients' lives.
5:15:51ENLex Fridman· 2026년 8월 26일팟캐스트 · 2명DHH Did Not Write a Line of Omarchy Quattro게스트 DHH · 진행자 Lex FridmanThirteen months after a skeptical conversation with Lex Fridman, the Rails creator describes how Opus 4.5, a swarm of coding agents, and a one-minute Linux installer ended his era of hand-chiseled Ruby.
3:12:58ENLex Fridman· 2026년 8월 12일팟캐스트 · 2명One Cold Shower, Twenty Champions: How Khabib Nurmagomedov Was Forged게스트 Khabib Nurmagomedov · 진행자 Lex FridmanIn a Makhachkala school gym, seventy men shared one shower, and the water was only cold.
3:46:18ENLex Fridman· 2026년 7월 28일팟캐스트 · 2명If You Take Slavery Out of the Picture, There Is No Civil War게스트 Gary Gallagher · 진행자 Lex FridmanIn 1860, enslaved people were worth more than every railroad and factory in the United States combined.
3:51:47ENLex Fridman· 2026년 6월 30일팟캐스트 · 2명Forty-Six Percent of Emperors Were Overthrown. The Empire Lasted Anyway게스트 Anthony Kaldellis · 진행자 Lex FridmanHistorian Anthony Kaldellis walks Lex Fridman through 2,200 years of Roman history and argues that what we call Byzantium was Rome itself.
2:53:42ENLex Fridman· 2026년 5월 29일팟캐스트 · 2명The Moon Is Falling. It Just Keeps Missing.게스트 Biggest Mysteries in Physics · 진행자 Lex FridmanFermilab physicist Don Lincoln tells Lex Fridman that the history of physics is a history of unification, and that antimatter, dark energy, and a theory of everything still sit far beyond the experiments we can run.