Can AI Crack the P vs NP Problem? A Complexity Theory Expert's In-Depth Analysis

In a Lex Fridman podcast, a discussion unfolded about the core challenge of computational complexity theory—P vs NP. The guest had participated in a debate on whether LLM-based approaches could make progress on the hardest problems in mathematics, such as P vs NP or the Riemann Hypothesis. A year later, his view has evolved: AI can clearly make progress on core problems in the field, but P vs NP may be exceptionally difficult.

P vs NP: A Problem Where Even Superlinear Lower Bounds Are Unknown

P vs NP asks: Are problems that can be solved in polynomial time through nondeterminism (e.g., guessing an assignment and then verifying it) also solvable in polynomial time by deterministic algorithms? Take SAT as an example: given a description of a formula (variables and clauses), is there an algorithm that can correctly determine whether a satisfying assignment exists in polynomial time in the input size?

Surprisingly, we don't even know any superlinear lower bound. Intuitively, SAT requires exponential time, but theoretically we haven't even proven an asymptotic result better than enumerating all assignments and checking them. The guest admits: "This problem is closest to my heart, but it seems very difficult to make progress on."

Nondeterministic Turing machines are a key computational model for understanding P vs NP. Unlike deterministic Turing machines, which can only perform one operation per step, nondeterministic Turing machines can "guess" multiple possible transitions at each step, accepting an input as long as there exists an accepting path. This is equivalent to allowing an algorithm to "guess" a solution and verify it in polynomial time. The class P corresponds to problems solvable in polynomial time by deterministic Turing machines, and the class NP corresponds to problems solvable in polynomial time by nondeterministic Turing machines; equivalently, NP is the set of problems for which a given solution can be verified in polynomial time. P vs NP asks whether these two classes are equal—that is, whether ease of verification implies ease of solving.

Worst-Case Analysis: A Powerful but Limited Abstraction

In complexity theory, "hard" and "easy" usually refer to polynomial time versus exponential time in the worst case. Worst-case analysis ignores the specific structure of inputs and attempts to provide a uniform algorithm for all possible inputs. This abstraction is extremely powerful; for example, the maximum flow problem can be solved efficiently in the worst case.

But the guest points out that it's questionable whether this abstraction is always useful. "Sometimes you really need more information about the structure of the instance to solve it better." This leads to the direction of "beyond worst-case analysis," which is considered a very important way forward for theoretical computer science.

Competitive ratio is a core concept in the analysis of online algorithms, used to measure the gap between the performance of an online algorithm, which does not know future inputs, and that of an optimal offline algorithm with full information. Specifically, the competitive ratio is defined as the maximum, over worst-case input sequences, of the ratio between the online algorithm's cost and the optimal offline algorithm's cost. A competitive ratio of c means that the online algorithm's cost will never exceed c times the optimal offline algorithm's cost. This is a worst-case guarantee and thus may be overly pessimistic, failing to reflect the algorithm's actual performance on typical inputs—which is exactly why the original text mentions that "the known tight upper and lower bounds are not ideal and far from the low cache miss rates of real laptops."

Online Algorithms and the Secretary Problem: Decision-Making Under Uncertainty

The secretary problem is a classic example of online algorithms: candidates arrive one by one, and you only know their ranking relative to previous candidates, not what the future holds. The goal is to maximize the probability of selecting the absolute best candidate. The optimal strategy is to wait for a period (observation phase) without making a decision, then choose the first candidate better than all previous ones. Under the assumption that the input order is uniformly random, the competitive ratio can be proven.

Another important variant is the paging problem: your laptop constantly processes memory requests and must decide what to keep in the cache and what to evict. Although algorithms with excellent competitive ratios can be designed, the known tight upper and lower bounds are not ideal and far from the low cache miss rates of real laptops.

An online algorithm is one that must make irrevocable decisions one by one on an input sequence without complete information about the input. The paging problem is a classic problem in online algorithms: cache capacity is limited, and when a requested page is not in the cache, a decision must be made about which page to evict. Common online strategies include Least Recently Used (LRU), First-In-First-Out (FIFO), and others. Competitive ratio analysis of the paging problem reveals the inherent gap between online algorithms and optimal offline algorithms, a gap theoretically characterized by the competitive ratio. This problem has wide applications in operating systems and database systems and is also an important model for understanding the limitations of online algorithms.

The Inverse Problem: How to Model the World

The guest believes there is an inverse problem here: rather than solving a well-defined worst-case problem, the question is how to model the world around us. "It's not about building a completely realistic model, but about how to formulate the problem in the right way so that it leads to interesting algorithmic problems that teach us about the world."

Algorithmic thinking is more important than ever in deciding where to dig deep. For example, factoring a random large integer is easy (half are even); what's truly hard are those special numbers that are the product of two primes.

The Role of AI in Hard Mathematical Problems

Returning to the original question: Can AI prove P vs NP? The guest does not give a definitive answer but points out that AI can clearly make progress on core problems. However, the peculiarity of P vs NP is that we lack even basic lower bounds, which may limit AI's progress. The broader implication is that theoretical computer science needs to focus more on modeling and problem formulation, not just on solving well-defined problems. This may be a key area for collaboration between AI and human mathematicians.

The inverse problem in the context of computational complexity refers to: given a real-world scenario in which we want an algorithm to perform well, how do we reverse-engineer a formal computational problem that both captures the real-world structure and is theoretically analyzable? This is the opposite direction from traditional complexity theory, which "starts with a problem and then analyzes its difficulty." The guest's emphasis in the original text that "it's not about building a completely realistic model, but about how to formulate the problem in the right way" is precisely a manifestation of this idea. The difficulty of the inverse problem lies in balancing the realism and tractability of the model: too specific a model is hard to analyze theoretically, while too abstract a model loses key structure. This perspective elevates problem modeling itself to one of the core tasks of theoretical computer science.

Conclusion

Solving P vs NP may still be a long way off, but the discussion reveals the frontiers of complexity theory: beyond worst-case analysis, online algorithms, and how to model the real world into computable frameworks. Can AI help? The answer may be indirect—by helping us discover better problem formulations and modeling approaches, rather than by proving directly.

One-line Summary

Even superlinear lower bounds for P vs NP are unknown; AI's contribution may need to shift toward problem modeling and inverse problems.

Paragraph Summary

Based on a discussion about P vs NP on the Lex Fridman podcast, this article points out that even superlinear lower bounds for the problem remain unproven, and that a direct breakthrough by AI may be very difficult. The guest emphasizes that worst-case analysis, though powerful, is limited, and that going beyond worst-case analysis is an important direction for theoretical computer science. Online algorithms (such as the secretary problem and paging) provide competitive ratio guarantees under uncertainty but still fall short of real-world optimality. The article further proposes the inverse problem—how to model the world—as more important than solving well-defined problems, with algorithmic thinking indispensable in problem formulation. The ultimate conclusion is that AI's role in hard mathematical problems may be indirect: helping discover better problem formulations and modeling approaches, rather than proving directly.