P v NP
In Our Time
00:00
The Graph Isomorphism Problem
There's a cut-off point where P and NP, who you're looking at each other, I'm asking you the right question. We don't know how to solve it, but if somebody could find a clever way of solving it, we wouldn't be able to translate that into an algorithm for solving the traveling salesman problem. There's another problem actually, this is a rather sort of timely discussion, called the graph isomorphism problem. And there's a little rumour going around as of yesterday or so, that somebody may have not completely solved it, but made an absolutely massive advance in our understanding. Wait till next Tuesday, and this person is giving a talk at the University
Transcript
Play full episode
