Read the article and sources →
Transcript
Auto-generated YouTube captions. They may contain transcription errors.
- 0:01 Sorting a list of a million names. A
- 0:03 computer does it in a blink. That's P.
- 0:06 Easy to solve. A giant sudoku. Checking
- 0:09 a finished one is quick, but solving it
- 0:12 can take forever. That's NP. Easy to
- 0:15 check. Are they secretly the same?
- 0:18 That's a million-doll question. For 27
- 0:21 years, computer scientists bet that one
- 0:23 wall could never be broken. Last week,
- 0:26 an AI model claimed to find a crack in
- 0:29 it. Start with a sudoku. If someone
- 0:32 hands you a finished one, checking it is
- 0:34 quick. Just scan the rows and columns.
- 0:36 But solving one from scratch can take
- 0:38 far longer. Computer scientists have
- 0:41 names for this. Problems that are quick
- 0:43 to solve belong to a group called P.
- 0:46 Problems whose answers are quick to
- 0:48 check belong to a group called NP. The
- 0:50 biggest open question in computer
- 0:52 science is called P versus NP. If an
- 0:55 answer is easy to check, is it always
- 0:57 easy to find, too? Most experts believe
- 1:01 the answer is no. Some puzzles really
- 1:03 are harder to solve than to check, but
- 1:06 no one has ever proven it. It's one of
- 1:08 the Millennium Prize problems with a
- 1:10 million dollars waiting for whoever
- 1:12 settles it. One of the most famous hard
- 1:15 puzzles is called ThreeAT. Think of it
- 1:17 as a lock with a row of onoff switches
- 1:20 plus a list of rules about which
- 1:22 combinations are allowed. The question
- 1:24 is whether any setting satisfies every
- 1:27 rule. The brute force approach is to try
- 1:30 every combination. But each extra switch
- 1:32 doubles the possibilities. With a few
- 1:35 hundred switches, there are more
- 1:37 combinations than atoms in the universe.
- 1:39 That kind of growth is called
- 1:41 exponential. In 1999, two computer
- 1:44 scientists Russell Impaglatso and
- 1:47 Rammoaman Paturi made a bold bet called
- 1:49 the exponential time hypothesis or ETH.
- 1:53 It says that for puzzles like threesat,
- 1:56 no clever trick can ever beat
- 1:58 exponential growth. You can speed things
- 2:00 up a little, but the work always
- 2:02 explodes. Hundreds of research papers
- 2:05 have been built on top of that bet. On
- 2:07 October 26th, OpenAI announced that one
- 2:10 of its internal AI models had found a
- 2:12 way to solve threesat slightly faster
- 2:15 than exponential. If it's right, that
- 2:17 breaks the wall. ETH would be false. The
- 2:21 model wrote out the proof and the team
- 2:23 translated it into a language called
- 2:25 lean, which lets a computer check every
- 2:27 logical step. One important catch, this
- 2:30 new method is still unbelievably slow in
- 2:33 practice. It changes what's possible in
- 2:36 theory, not how fast your laptop works
- 2:38 today. Here's the twist. The people
- 2:40 reviewing the claim are the ones who
- 2:42 made the bet. Impalatu and Puri from UC
- 2:46 San Diego are leading the review with
- 2:48 Ryan Williams from MIT. They've been
- 2:51 clear that agreeing to check it doesn't
- 2:53 mean they agree it's correct. The review
- 2:55 is open so other researchers can check
- 2:58 the work, too. Some things this does not
- 3:00 mean. It doesn't solve P versus NP.
- 3:04 Puzzles like threesat could still be
- 3:06 hard, just not as hard as ETH claimed.
- 3:09 It doesn't break the encryption that
- 3:11 protects your bank account, which relies
- 3:13 on different math problems. And it won't
- 3:16 make any software faster tomorrow. So
- 3:19 why does it matter? If the claim holds
- 3:21 up, computer scientists will need to
- 3:23 re-examine every result that leaned on
- 3:26 that wall. It would be one of the
- 3:28 biggest surprises in the field in
- 3:30 decades. And it might signal something
- 3:32 bigger. AI working alongside human
- 3:35 experts on problems people have been
- 3:38 stuck on for years. For now, it's a
- 3:40 claim, not a confirmed result. The
- 3:43 experts are checking, and we'll know
- 3:45 more soon.