Can AI solve P vs NP? | Lex Fridman
A discussion on whether AI can solve the P vs NP problem, exploring complexity theory's hardest questions, the limitations of worst-case analysis, and the importance of moving beyond worst-case thinking to model real-world problem structures.
Summary
The conversation begins with a question about whether AI can make progress on the P vs NP problem, described as the central question in complexity theory. The speaker expresses skepticism about AI solving this particular problem, noting that fundamental challenges remain: we don't know any super-linear lower bounds for the satisfiability problem, despite believing it requires exponential time to solve.
The discussion then pivots to explaining what makes problems 'hard' versus 'easy' in computational terms. P versus NP refers to the question of whether problems solvable with non-determinism (guessing an assignment and checking it) can also be solved deterministically in polynomial time. This introduces the concept of worst-case analysis, where algorithms are evaluated against the most difficult possible inputs rather than average or typical cases.
The speaker uses a marriage analogy to illustrate why worst-case analysis might be counterintuitive: evaluating a marriage decision based on the worst possible outcome may not be the most practical approach. The secretary problem is mentioned as an example of online algorithms where decisions must be made with incomplete information.
The core argument presented is about 'beyond worst-case analysis,' a direction the speaker advocates for in theoretical computer science. While worst-case analysis has been 'spectacularly powerful' in identifying efficiently solvable problems (like max flow), it may not capture how real-world instances actually behave. The discussion uses the paging/caching problem as a concrete example: algorithms proven tight for worst-case competitive ratios perform far worse than actual laptop caching, suggesting real-world memory access patterns have structure that worst-case models ignore.
The speaker frames this as an 'inverse problem'—instead of being handed well-formulated problems, researchers must now figure out how to model natural phenomena in ways that lead to productive algorithmic insights without over-modeling or under-modeling reality. The final point notes that factoring numbers illustrates this principle: factoring random large numbers is easy (half are even), but factoring numbers that are products of two primes of similar size is hard, showing that problem difficulty depends critically on instance structure.
Key Insights
- We currently cannot prove super-linear lower bounds for the satisfiability problem, despite believing it requires exponential time—we only know it's at least as slow as reading the input.
- Worst-case analysis abstracts away fine-grained details about problem instances to solve all possible inputs uniformly, which has been powerful but may miss how real-world instances actually behave.
- Theoretical algorithms with tight worst-case competitive ratios for caching perform much worse than real laptop caching systems, revealing that realistic memory access patterns have exploitable structure not captured by worst-case models.
- The field needs to shift from purely solving well-defined problems to using algorithmic and mathematical insights to determine which aspects of real-world phenomena to model—an 'inverse problem' of deciding what level of detail matters.
- Problem difficulty is highly dependent on instance structure—factoring random numbers is easy, but factoring numbers that are products of two similarly-sized primes is hard, demonstrating that worst-case assumptions miss critical distinctions.
Topics
Transcript
[0:02] - Uh, speaking of crises, let me get back to P versus NP question Ankur was talking about. Do you think-- how hard of a problem is that, proving-- So this is sort of the central question of complexity theory, P equals NP. Do you think AI will be able to prove this? In fact, we should mention that you're kind of a part of a panel. There was initially a debate about whether LLM-based methods, could one day make progress on the hardest [0:34] problems in mathematics, like P and NP or the Riemann hypothesis. That was a year ago. So what is your updated view on this? - Well, clearly, they can make progress on- ... central…
Full transcript available for MurmurCast members
Sign Up to AccessMore from Lex Clips
GTA 6 review by biggest jewelry thief in US history | Larry Lawton and Lex Fridman
Larry Lawton, a legendary jewelry thief and FBI's most-wanted criminal, discusses his extensive experience robbing stores while reviewing GTA 6's trailer with Lex Fridman. He provides detailed critiques of the game's accuracy regarding criminal operations, casing techniques, and security vulnerabilities, while reflecting on how his past crimes cost him years with his children.
Robberies in GTA 6 - jewelry thief explains | Larry Lawton and Lex Fridman
Larry Lawton, a former jewelry thief, discusses his criminal expertise with Lex Fridman and explains what he wants to see portrayed accurately in GTA 6's robbery mechanics. He emphasizes that successful robberies depend heavily on meticulous casing and understanding human behavior patterns rather than just technology.
US war against China or Russia: Why military experts are wrong | Lex Fridman Podcast
Military analysts often make prediction errors by abstracting military power as a simple ranking rather than understanding how forces interact in specific contexts. The Ukraine-Russia war exemplified this, as analysts underestimated Ukrainian military capability and overestimated Russian performance, partly due to having more intelligence on Russian plans than Ukrainian defenses.
Is Putin being lied to? - The distortion of information in Ukraine war | Military Analysis
The transcript discusses how Russian military forces systematically overstate territorial control through false reporting, creating a cascading problem where fabricated battlefield data leads to poor operational decisions, increased casualties, and potentially misinforms political leadership including Putin. The speakers contrast this with Ukrainian practices and explore broader patterns of information distortion in military hierarchies across historical conflicts.
North Korea's role in Ukraine war | Military Analysis - Lex Fridman Podcast
The speaker analyzes how external support sustains both Russia and Ukraine in the war, with North Korea providing significant military aid to Russia. While Russia has resources to continue fighting into 2027, its economy faces structural problems as 44% of government spending goes to military efforts. Ukraine's main vulnerabilities are economic damage, population displacement, and dependency on Western financial, military, and intelligence support that remains subject to shifting political priorities.