OpenAI’s nameless model just changed the odds of P = NP...

Main Ideas

• The video describes a claimed result that challenges the Exponential Time Hypothesis (ETH), a long-standing assumption in theoretical computer science.
• ETH says that solving 3-SAT—a problem involving true-or-false variables and rules requiring at least one of three variables to be true—cannot be done in subexponential time in the general case.
• 3-SAT is NP-complete: a sufficiently fast algorithm for it would yield fast algorithms for every problem in NP. This is related to, but stronger than, the unresolved question of whether P = NP.
• ETH has been useful for proving limits on other algorithms. The video says more than 800 papers rely on it, including results about finding mutually connected groups and solving the traveling salesperson problem.
• According to the video, an unnamed OpenAI model produced an algorithm for 3-SAT with running time roughly (2^{n/\sqrt{\log n}}). That is still extremely slow in practice, but it is subexponential, so it contradicts ETH as stated.
• The reported practical impact is currently negligible: the algorithm would not outperform brute force until an input size exceeding (10^{10{,}000}). The result therefore changes a theoretical assumption, not what can feasibly be computed today.
• The video says Scott Aaronson raised his personal estimate that P = NP from 3% to 5%. This is presented as a modest change in his judgment, not as evidence that P = NP has been proved.
• The paper’s authors reportedly asked the original ETH researchers to check the proof. The video says they were unpaid, and that an early draft was difficult to read and had to be rewritten.

How the Claimed Algorithm Works

The video contrasts the new approach with the usual search strategy:

1. Search through assignments: A conventional method tries possible truth-value settings and checks whether each satisfies all the 3-SAT clauses. Brute force takes (2^n) possibilities; clever algorithms have improved the base, but still have exponential running time.
2. Count solutions instead: Rather than searching directly for a satisfying assignment, the model reportedly reframed the task as calculating the total number of satisfying assignments—a large sum.
3. Break the calculation into pieces: It modified the formula so the rules, or clauses, no longer depended on one another. This made it possible to count solutions for separate pieces independently.
4. Recover the original count: It then used Hermite interpolation, a mathematical technique dating to the 19th century, to reconstruct the exact solution count for the original, unmodified formula.
5. Use the faster computation: The resulting algorithm’s subexponential running time is what contradicts ETH.

Sponsor Segment

The video also promotes Warp Factories, a cloud platform for building software workflows with coding agents. It describes configuring repositories, secrets, agents, automations, and sandboxes as code; comparing models with benchmarks based on a team’s own tasks; and Warp’s claim that it reduced its agent cost per pull request from $80 to $20.

Speakers and Sources Featured

• Fireship / The Code Report narrator — Presents and explains the story.
• Dan Roberts — OpenAI physicist credited in the video with publishing the paper.
• Unnamed OpenAI model — Credited with producing the algorithm.
• Sebastian Bubeck — OpenAI researcher, quoted as calling the result the biggest surprise of his 20 years following computer science.
• Scott Aaronson — Complexity theorist whose reaction and changing estimate of P = NP are discussed.
• Russell Impagliazzo and Ramamohan Paturi — Identified as the researchers associated with the 1999 ETH formulation and later asked to verify the proof.
• Unnamed UCSD PhD student — Described as making urgent thesis edits after learning of the result.
• Warp — Sponsor featured in the advertisement.