Computer Scientists and Mathematicians Are Stunned by Chicago Professor Laszlo Babaiâ€™s New P vs NP Graph Isomorphism Proof
Joyce Park stashed this in Code
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).