▶ YouTube Summaries

• YT :: https://www.youtube.com/watch?v=Ka0p5tUUmgg
• Original title :: This is Crazy

ThePrimeagen explains OpenAI's announcement that an internal model disproved the Exponential Time Hypothesis (ETH) by solving 3-SAT in sub-exponential time. The video walks through 3-SAT with small Boolean examples, why the exponential growth of guessing matters, and the NP, P, NP-hard and NP-complete classes. It then lays out the theoretical consequences if the result eventually led to polynomial time: broken RSA, SHA-256, HMAC and blockchain on one side, and fast protein folding and drug research on the other. The tone is half-joking; the practical message is that the result is a small step and not yet a threat.

The announcement

• OpenAI announced three discoveries in mathematics, computer science and physics: local smoothing for the Kakeya conjecture (harmonic analysis), a complexity theory result, and the existence of quantum chromodynamics and completions of the standard model.
• The video covers only the middle one: the Exponential Time Hypothesis is false.
• Source: OpenAI post on building scientific understanding with academic communities.

3-SAT and the Exponential Time Hypothesis

• 3-SAT: a Boolean expression made of groups of three variables joined by OR, groups joined by AND; the task is to find variable values that make it true.
• With one group (A or B or C), setting any variable to true satisfies it. Adding groups and variables (A to G in the example) forces more and more guessing, since each new variable multiplies the number of candidates to check.
• ETH states that 3-SAT is bounded exponentially (about 2^n). It was never proven, only hypothesized, and if true it implies P does not equal NP.
• Clever algorithms already lowered the base to about 1.3, but 1.3^2500 still exceeds the number of atoms in the known universe, so such instances are uncomputable.
• OpenAI's result gives a running time of roughly 2^n divided by the square root of log n. This is sub-exponential: still not polynomial and still hopelessly large for big n, but it grows slower than any fixed exponential, which contradicts ETH.
• The open question is whether this is the first of many reductions. As precedent, an integer multiplication proof among the many OpenAI proofs from 6 October started with a tiny improvement and was followed within weeks by a stream of further improvements.

NP, P, NP-hard and NP-complete

• NP: problems whose solutions can be verified in polynomial time. A 3-SAT assignment is checked quickly by eye even though finding it is exponentially hard.
• P: problems solvable in polynomial time. The big question is whether all of NP is in P.
• NP-hard: problems at least as hard as every problem in NP.
• NP-complete: the intersection, NP-hard problems that are also verifiable in polynomial time. 3-SAT is NP-complete.
• Any NP-complete problem can be encoded as any other. The traveling salesman problem can be expressed as 3-SAT, which is why the 2,500 example is described as the size of the United States as a 3-SAT formula. Solving one in polynomial time would solve all of them.

Consequences if P equals NP

• Cryptography: RSA relies on the difficulty of integer factorization, which is in NP and checkable in polynomial time but not solvable in it. Polynomial-time solving would let powerful computers break public key encryption across the internet. The same applies to SHA-256, HMAC, pseudo-random number generators and blockchain.
• Science: protein folding is described as NP-complete, so research taking decades or centuries could shrink to about a year, with cancer cures given as an example.
• Even Sudokus would become solvable in polynomial time.
• Framing: P equals NP would be the craziest possible world, both catastrophic and wonderful. The sub-exponential result is only a first step towards that, not proof of it, and the speaker admits to simplifying RSA details.