Big step forward in P vs NP! Go University of Chicago!

Wow, this is a big deal. First big breakthrough in computability in a long while!

Last month they covered a famous math question, the P vs. NP problem. It’s an arcane problem, though famous enough that it turns up as a Simpsons joke. And its implications are genuinely immense.

What is P vs. NP? While it’s one of the hardest unsolved problems in math, it’s conceptually very simple. Start with Wikipedia’s definition of the problem: “Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.”

Why is that a big deal? Crudely speaking, computer security as we know it is based on computers being able to verify problems quickly but not solve them. Or, in short, NP (easily verified) does not equal P (easily solved).

But if P does equal NP, computer security goes boink (in very broad terms). It’s such a big deal in math that anyone who solves the P vs. NP problem gets one million dollars.

Not exactly light listening for the commute, but I figured it was as far away from thinking about my job as possible. But during the middle of the episode, one of the guests broke some news: A big breakthrough in the P vs. NP problem was rumored to have been made, and was about to be presented at the University of Chicago.

Fast forward a couple weeks, and I get a message from a colleague—her friend had tweeted a math lecture, and it had gone viral: a “livetweet of Babai’s first Graph Isomorphism talk.” Would I be interested? The tweets were incomprehensible to me, but recognizable as the big P vs. NP breakthrough I’d randomly heard about on In Our Time.

My math education basically stopped somewhere within calculus. I literally failed the math entrance exam at the university that László Babai—the computer scientist and mathematician behind the breakthrough—teaches at. But his discovery is a really, really big deal:

“My first thought was that this was a joke. I checked the month to make sure it wasn’t April,” says Ryan Williams, a Stanford University computer scientist. “It’s a huge jump in our understanding of the problem.” He says the discovery is potentially the most important theoretical computer science advance in more than a decade.

Caveat: theoretical computer science. It might not change anything for us mortals. But neither do a lot of amazing things that people do, like freeclimbing a mountain no one thought possible. So I thought I’d at least figure out what the big deal was, with some help from the guy who live-tweeted it, Gabriel Gaster, a data scientist at Datascope (I’d previously talked to him about his map of Divvy traffic patterns).