OpenAI Claims Math Result That Keeps a Computer Question Open
The 175-page paper challenges a 27-year-old assumption about hard problems, but outside experts are still checking it.

All-In with Chamath, Jason, Sacks & Friedberg · Midterm Blood Bath, $4T AI Sell Off, Data Center Freeze, What's Next for TrumpOpenAI has claimed a result that could keep one of computer science's biggest questions alive, but outside researchers are still checking whether the proof holds.
David Friedberg, an investor and host on a tech show, put it this way: "can a problem be solved with a computer?" and "how long does it take?", calling that "the most fundamental question in computer science."
The time it takes decides whether a problem can practically be solved.
One group is called P. These are problems a computer can solve in what is called polynomial time, where the work grows in a manageable way as the problem grows, like the size squared or the size cubed.
The other group is called NP. These are problems where a proposed answer can be checked very quickly, even when finding it is difficult. His example was a large Sudoku puzzle that can require extended work to solve, yet a finished grid can be checked in a couple of seconds.
The central question is whether P equals NP. In plain terms, could every problem with a quickly checkable answer also be solved quickly. If so, then every problem could in principle be solved by computer.
A related idea, called the exponential time hypothesis, was proposed in 1999. Friedberg said it held that a particular logic puzzle known as three-SAT takes exponential time, meaning the work rises sharply with size, like a number raised to the power of the size.
That hypothesis implied an entire class of problems could never be solved quickly, which would mean P does not equal NP. Friedberg said OpenAI, in a 175-page paper, claimed to disprove that hypothesis for that problem by solving it in sub-exponential time, or faster than exponential growth would predict.
If that claim holds, he said, P could still equal NP. He also stressed that the paper was still being evaluated by outside researchers and had not yet been fully verified. Accounts cited in the discussion differed on the speed of the work, ranging from less than 10 days to a few hours.
Questions people ask
What is a three-SAT problem?
It is a type of logic puzzle in which a computer must decide whether a set of true-or-false conditions can all be satisfied at once. Larger versions add many more variables and conditions. It is often used to study how solving time grows with problem size.
What does sub-exponential time mean?
It means faster than exponential growth, but not necessarily fast in everyday terms. The solving time still grows as problems get larger, only less explosively than feared. Researchers care because the growth rate decides whether very large problems stay out of reach.
Would this result prove that P equals NP?
No. At most, the claim would leave P equals NP possible by removing an argument against it. Friedberg stressed the 175-page proof is still being evaluated by outside researchers and has not been fully verified.

