I want to start by talking about a very concrete problem that is rather taxing. So I want you to imagine that you're planning a party. So a huge family party with let's say a hundred guests, and as part of it, you're going to have a big dinner and you want to sit everybody together around a table. So it sounds like a lovely idea, possibly. You'll be amazed to hear that in this particular extended family, there are some groups of people that don't get on so well with other groups of people. And you really don't want to sit certain people with differing opinions about the state of the world, say, next to each other. So there are people that you really don't want to sit side by side. Now I wanted to give a concrete example here. Well, not very concrete, imaginary, because I'm a pure mathematician, but I wanted to give you an actual family. So I'm not going to put up a hundred because that would be impossible to process. So let's instead have a smallish family that's just got uh nine people up there for us to think about. So I've given each person just letters, but that's Auntie Alice, and she's uh you've also got Bill. Two of the important people that are going to feature later are Granny in the bottom corner there, and and Uncle Ian. Um so Alice is okay, sat next to Bill and David, but really won't get on if you sit her next to anyone else. Bill is somewhat more gregarious, and so there's four people that Bill's willing to sit next to. C might as well be me, I guess. I'm quite gregarious, so there's four people I'm willing to sit next to. And there's the rest of the table. So we've been given some data. And the first thing that happens when you look at this probably is you think, oh, that's too complicated. I can't really try and work out from that horrible table how on earth I'm gonna find a table arrangement such that blood has not been shed by dessert. Um so what do we do? Well, we're gonna first of all represent it in a way that's gonna make this problem easier to solve. So this I've just put nine up. Somebody, after I talked about this once before, sent me free access to some software that had been used to see 6,000 people once a dinner. So this is a thing, people pay money for it. Um, and they pay money because as the dinner gets bigger and bigger, it gets harder to solve. So, what I'm gonna do is model this problem as a graph, which means I draw a pretty picture. So, this is the same data as there was on the previous slide. Uh I mean, you may not think it's pretty, my hand-drawn pictures are terrible, that's why I don't do something more applied. Um, but what I've got here is I've got a dot for each person. Um, so there's Auntie Alice at the very top, and there's me middle-ish in the center. Everybody's got a dot. Um, and I've put a line, which is called an edge, uh, connecting two people if they won't fight at dinner. Now, these pictures have names, they're called graphs, and so I've I've put the words up there. The dots are called vertices, because I am absent-mindedly going to use that word, so let me tell you it now. And the lines are called edges, and an edge is just a line connecting two of the people. So those are people that I can sit side by side. And now that we've got this drawn pictorially, we can think of what we're doing. Our seating plan for dinner is we want to find a way to walk around this graph. So walking around the graph is going to correspond to walking around the table. Don't mind what direction we do it, walk around the graph in two different directions if we want. So we want to walk around the graph, starting at Auntie Alice, say, such that, well, each person should be sat at the table, because otherwise we haven't got a seating plan, and everybody should only be sat in one place at the table. Nobody is shuttling backwards and forwards trying to keep two people happy. So we should visit each vertex exactly once and eventually get back to the beginning again. That corresponds to going all the way around the table and returning to Auntie Alice. And so if we look at this picture, you can start to see that we're gonna have a problem. So the problem that we're gonna have is that Auntie Alice can only sit next to Bill and David. Those are the only people that so we have to put her between them. And then we look at what's going on with Bill. Well, he could sit next to lots of people, but Granny will only sit between him and Hattie. So we have to then put Granny the other side of Bill because Alice has grabbed one side of Bill. And then looking further ahead over there, Uncle Ian is also problematic because he will only sit between Hattie and David. And once I put those six people in, well, I've closed my circuit. I've reached the other side again of Auntie Alice, and I haven't managed to fit the three people in the middle around the table. So we can see that sadly, this family can't actually manage a dinner without people fighting. So then what are we going to do? Well, if you think a bit harder again, you'll realize that we wouldn't have to change the family very much to make things work. If I could just persuade Granny and Uncle Ian to please start talking to each other again, then we could instead seat the whole table by putting Alice there and she's next to Bill, that's not changed. And then Bill will be next to Granny, that's not changed. So far, my frowny face is still not very happy. Um, but now from Granny, I could loop right the way over to Ian if they'd become friends. And from Ian, I could go back to Hattie, and then we can from Hattie we can now dive into the middle and pick up three more people before finally going to David and then back, back to Auntie Alice again. So if we had one more edge in there, we could do a fight-free dinner. Now, the reason why this problem is hard is that if you would just start trying to fill names in round a dinner, you can see that there are lots and lots of possibilities. I've made this one look not too difficult by having some very, very picky people that could only sit next to two. But if I had a thousand people and lots of people could sit next to say 400 but no more, you would sit your first person and then have 400 choices for who went next to them, and then maybe have 399 choices for who went next to them, and then maybe back up to 400 for who went next to them, and you would wind up losing yourself in possibilities. So, what would you do? Well, you'd try putting it into a computer. This is exactly the kind of thing that computers are for. So let's start with the real birth of computing. Uh, here's Alan Matheson Turing, uh, who's often credited as the creator of computers. So in 1937, he's we describe it as in his early 20s. Uh, he invented a theoretical computer, which is still the model that we use to model every single real-world computer in existence. It's the model that I teach my undergrads. Um, and he was imagining this way before any computer was real. But he came up with the idea of a machine which could be given instructions which let it do anything. So until then, we had machines for particular purposes. So you might have calculating type machines or various things that could do things that looked a bit like calculations, but they could only do the one thing. There were certainly electronic cache registers and stuff were around. What he came up with was the idea of a machine where you could give it a set of instructions that would let it pretend to do this problem, and then the next day solve a different problem, and then the next day solve a different problem. So this is a theoretical computer which still models every kind of real-world um computer. Now, the simplest kind of questions to try and answer uh problems about are ones where the answer is just yes or no. Nothing complicated in the output. I'm not asking something to please generate me an AI image or something like that. I just want to know, can we get to yes or no? Break it down to the simplest possibility. And Turing proved in 1936. So this is sorry, I'll put two dates there. One is kind of when he did it, and one's when when more details came out. Um, he showed that there exist yes-no problems, so things where the answer is going to be yes or no, that are mathematical kinds of problems that seem like the kind of things you might want to solve, which could never be solved on any computer. So this was one of the fundamental shifts of 20th century mathematical thought. We went from just saying, how do I solve this problem, to saying, can this problem be solved? Could there be a solution to this problem? I'm not going to ask if it's yes or no, I'm going to ask if you can find it. And at this very young age, he proved that there are problems which can't be solved. And he did so by showing something quite concrete. So, in this wasn't his language, but in in modern terms, he showed that no computer can test whether a given program, if you load up the program and put some particular input into it, no computer can test for all possible programs and all possible inputs whether the program's gonna stop or run forever. So whenever you get a spinny wheel of death on a computer screen or a little egg timer or whatever, depending on what software you use, it's mathematically provable that that might always happen. That it is not possible to write one piece of code that can test all possible programs and see whether or not they stop. Sorry, this is quite depressing news for the beginning of the talk, but we'll get cheerier later. And it turns out once you know one problem like this, these are called undecidable problems, you can make lots and lots of other ones. So for a slightly less uh serious thing, I'm guessing, given that you've come to a maths talk in your spare time, at least some of you play games like Magic the Gathering. It's actually impossible to decide whether a player has a winning strategy in Magic the Gathering because the game is, you can you could add more and more packs of cards to it. It's not a finite game in some sense. I mean, any particular game is finite, but there's no upper bound on how big it is. Uh, it is a theorem that Magic the Gathering is undecidable. Um, and just because this comes up a bit recently, so quantum computers have been very much in the news. Uh, I said that we we still use Turing machines to model computers, and that's because it's a theorem that if a problem can't be solved on a standard computer, then it can't be solved on a quantum computer either. So Turing's theorem still holds true for that. I'll talk a bit more about quantum computers in a bit, but for now, that theorem is still there. Anyway, so the 30s we get the birth of computing, and then over the next few years, well, A, people start proving that lots and lots of problems are undecidable, but B, people actually build computers and start using them to do stuff. And it becomes apparent that we need to have some theory about if a problem can be solved on a computer but it's gonna take 200 years to get the answer, then in practice it can't be solved. So even if a problem can be solved, we really might care how much time it's gonna take to solve it. So both in a good way, uh, cryptography relies on problems being hard to solve by computers, and in a bad way, sometimes we really want to solve things, and knowing that no program can do so is is useful information because it means that maybe you don't try and get a perfect solution but a close to good enough solution rather than the ideal one. So, how do we go about measuring this difficulty? Well, imagine I give you a couple of three-digit numbers to add together. What do you have to do? Well, roughly speaking, you add up the numbers in the same columns. So you add up the units, you add up the tens, you add up the hundreds. Um, so that's three single-digit additions, and then carries are somehow a bit special because they're just plus ones. So carries you can imagine as sort of not counting, they're much cheaper than actually adding up numbers. So if I were to give you a 20-digit number and a 25-digit number, you can immediately say, well, I'd need to do about 20 single-digit additions, and then a bit of carries and stuff. So the the cost of doing addition just depends on the length of the numbers. How many digits did you type in? Okay, it's proportional. So we don't care exactly how many things are going on on a very fine-grained level, but it's proportional to the number of digits that we're messing with. To do multiplication, if you cast your mind back to having had to do long multiplication at some point, what do you do? Well, you multiply each digit in the first number by each digit in the second number, and then you do some shuffling things sideways, and then you do a bunch of additions. So for this particular pair of numbers, that's nine, so three for the first times three for the second, nine single digit multiplications, which you can imagine you might just look up, right? Imagine you were you were a computer and you were very stupid, you'd go, oh well, three times nine, I've got that, that's 27. Um, and then some some additions. So in general, if I were to say, here's one very big number and here's another very big number, now multiply them, you'd know that the amount of work you had to do was proportional to the product of the lengths of the numbers. So for addition, it was just one of the lengths, and for the multiplication, it's the product of the lengths. So in general, we talk about a class P of problems, uh which can be solved in time that's bounded by, well, some polynomial of the input size. Um a polynomial is just taking the input size, so the number of digits, say, for either addition or multiplication, and raising it to some power. So for addition, I raised it to the power one. It just was the number of digits, just leave it alone. For multiplication, I squared it. It was the product of the two numbers. So if I can do it by raising to some power and then maybe adding some numbers and adding a constant, say, then we call that being in p. So this concept was was first defined by somebody called Jack Edmonds in the 70s, um who posited then that it was the class of problems which are somehow solvable in in a reasonable amount of time. So let me show you why, because you might think, well, polynomials can get quite big. If I'm raising some number to a big power, it gets quite big. So let me give you a bad, bad polynomial. We don't know many polynomial time algorithms uh that run in anything much faster than n to the five. Somehow they they run out. So n to the five is a very bad polynomial, and then two to the n, well that's that's an exponential function, so that's not a polynomial. And let's imagine, for the sake of argument, this is the input size as the various values of n. So input size 2, maybe it's a two-digit number. Input size 10, maybe it's a 10-digit number. And for convenience, I'm going to assume that my computer does roughly a thousand operations a second. The actual answer I looked it up is 32 trillion, but I don't want numbers that big on the slide or numbers that small on the slide. So let's call it a thousand between friends. So if I put in a fairly small problem, size two, well, two to the power of five is thirty-two, we can do that. Um, and so my n to the five thing takes 32 milliseconds, 32 thousandths of a second. Uh 2 to the n, well, that's 2 squared when I plug in n is 2. And well, that's 4. So I was claiming that polynomial was worth better than exponential, and it really isn't. But maybe that's because 2 is too small. I mean, like messing around with two-digit numbers doesn't really tell you what's going on. So let's pump up to 10. 2 to the 10 is about a thousand, so let's call that about 100 seconds. I'm being very rough and ready here. Um, 10 to the 5, that way around, is about 100 seconds. I'm being quite rough and ready here. 2 to the n, that's 2 to the 10 milliseconds. That's about a thousand. Sorry, I got my my rows the wrong way around. So that's about a second, and still this n to the five is winning. But I did say I picked a very bad polynomial. So let's bump up to 30. Uh, if I wanted to do something with input size 30 and it was gonna take to the power five, then it would take my computer six and three-quarter hours. So that's suddenly an amount of time which you'd be willing to do that occasionally if something was really important, but you're not casually gonna do it. Um, I tend to describe efficient algorithms as ones that finish in the time it takes to go and fetch a cup of coffee, and that would be quite a serious cup of coffee. Um whereas my two to the n table, well, 12 and a half days. So suddenly we're just in completely different units of measurement. And by the time I got up to 100, so that's only three and a bit times bigger than the previous size. My n to the five, well, it's still looking bad. That's now 115 days, but my two to the n is 17 centuries. So as the size gets bigger, two to the n starts being completely impractical. Like things don't need to get very big before something that runs in two to the n is just something you can't do. Maybe you can split it across lots of computers, but 17 centuries is going to take a lot of computers to break things down to a reasonable size. And if you did have enough computers, then I'll come along and go, well, what about a problem of size 200? Can you do that now? And you'll need a lot more. Okay, so this is how we measure how hard problems are. It's it's how long would it take a computer? And I have to allow the size of my problems to get bigger and bigger to make sensible statements. If you talk about a single problem, I could have just stored the answer. Oh, I could just give you the answer. So there has to be some big collection of problems. Okay, so let's do a little diversion into one place where we use computationally hard problems. So to me, Turing is a god because of the invention of computers, but probably to much of the rest of the UK, Turing's really important because he arguably is describable as the person that helped Britain win World War I more than almost any other individual. So he's famous as the person that broke the Enigma code. So this is a picture of an Enigma machine. So this was the code that was being used uh by the Germans, and and Turing managed to work out how to break it using machines. Um we don't use this to encrypt messages anymore. The main way since World War II that we use to encrypt messages uses a problem which is very easy to solve in one direction, and we believe is quite hard in the other. And so let me tell you the problem and then I'll briefly explain the significance of easy in one direction and hard in the other. So a prime number is a whole number bigger than one, you're not allowed to pick one, such that the only numbers that divide it are one in itself. Every number is divisible by one, that doesn't count. Every number's divisible by itself, that doesn't count, but nothing else should divide it. So for example, two is prime, because there's no other numbers smaller than it than one and itself. Three is prime, only divisible by one and three. Five is prime, only divisible by five, and according to my computer, that number is prime. So there's infinitely many primes, they don't run out. That's been known back to the Greeks. Some numbers that aren't prime, for example, include four, because I can divide it by two, and two isn't one and isn't four, so six, somebody's mushering, yes, six comes next, so that's definitely not prime. Uh some numbers are easy, so this is clearly divisible by ten. All right, you don't need to look very hard to see whether that's divisible by ten. Uh, some numbers are less easy. Um, so there's a biggish number. And if you fire up something designed to do maths, you will find out quite quickly that this is a product of those two and that both of those two numbers are primes. If you ask ChatGPT, it will keep talking at you for about 10 minutes. It will tell you various ways that you can test numbers for primality, and eventually it will tell you to go away. Um Claude did do better. Claude uh spun up a separate math system that answered it rather than Claude answering it itself. So these problems are hard for all kinds of computers. So, what do we do? Each of us, if you want to um communicate, say with your bank, your bank will publish a big number that's a product of two primes. You use that big number, which anyone can see to encrypt a message and send it to the bank. The bank knows what the two primes are and can use the knowledge of those two primes to work out what you're saying. So everybody can advertise a big number and secretly know how to make it. Um, there's a bit more going on than that, but it's a slight sidetrack. But yeah, easy in one direction, seems hard in another. Multiplication is easy, anybody can multiply. Factoring is hard. Let me talk about one more very practical. I'm aware everything I've been talking about maybe sounds a bit more playish. So here's a real-world thing. You run a factory with three machines, you get into work one morning, and a whole load of jobs have come in overnight to be run on the machines, and here's a big table of jobs. Uh and what you want to know is can you run them all by five o'clock? Can you finish them all today? Uh so I've handily told you there's 480 minutes that we've got to play with. Um, and the reason I put this problem up is A, it's hard, B, it's practical, and C, I want to tell you how we actually solve these problems in practice. So we do them on computer and we use a technique called backtrack search. So back when I was working in AI, backtrack search was one of the main things I worked on. So what do you do? You assign jobs to machine one until it's full. So I give it A and B, that adds up to 450, which is not yet 480, but there's nothing else that will finish before five o'clock. So I give it a and b and then stop. And then I give some jobs to C to machine two, and I do the same thing. So the first job I haven't assigned yet is C, it needs to go somewhere. Let's give it to machine two, and then I keep giving machine two jobs until machine two is full. So I give it C and then D, that takes it up to 310. Can't give it E, that'll take too long, but I can give it F. And then I look to see how much is left and discover machine three won't finish. That's not gonna work. So what we do is something called backtracking. We say, well, when When I gave those machines those jobs, I did something stupid. I need to unpick my most recent decision. And my most recent decision was the stuff I gave machine to. So let's try unpicking that. I gave it C D F. Let's not give it F. Let's try giving it C D G instead. Well, you can see G is actually quicker than F, so that's gonna be even worse than giving it C D F was. Okay, well maybe the problem was C D. Let's try giving it C E. Well, if I give it C E, I'm up to 410. There's nothing else I can give it. C F, that's not gonna work. C G that's not gonna work. C H that's not gonna work. Properly backtrack. Problem must be occurring with the assignment to machine one. So I gave it jobs, A and B, and now I've tried everything with giving it jobs, A and B, and we didn't get anywhere. So let's try giving it A and C. Well, you're gonna keep trying things, and trust me, that's not gonna work. Okay, let's not give it A and B. And I know this is taking a while, but this is really what computers do. So we'll give it A and D, and then there's room to squeeze in E as well. Now I try assigning to machine two, and it can have B and C, and then I assign to machine three, and they fit. And so lo and behold, we have achieved success. So I wanted to show you that, even though I it's a bit dry, but this is literally how we wind up solving most of these hard problems. There are various clever tricks you can do to make it better. There are strategies like give it the biggest job first, hand those out across all of them, for example. Um but no matter what strategy you apply, at some point ultimately you're gonna try something like this. And this is maybe how you, when you're really stuck solve sudoku's, you just start saying, well, maybe it's either a two or a four. So let me put a two in and then see what happens, and then if that doesn't work, I'll try changing the two to a four and see what happens. So ultimately, we come down to we're not quite testing all of them, but we're testing most possibilities until we find one that goes. Okay, I think I've now told you enough to introduce P versus NP. So the famous pair of problems. I've told you about P. These are the problems we can solve in polynomial time, and a good way of thinking about what polynomial time means is practical. These are the things we can solve. This is the stuff we can do. What's NP? Well, it doesn't mean not practical exactly. Um, it actually means non-deterministic polynomial, but that's not very helpful at this point. So a decision problem, a problem with the yes-no answers in NP, if whenever the answer's yes, there's some kind of proof that that answer is yes that we can check in polynomial time. So it's not that we can find the proof quickly, it's that if there is a proof and somebody just walks into the room with it and shows it to us, we can test it quickly. Okay, this may not seem like a very practical definition, but it turns out to be useful. So if an angel appeared from on high with the solution, you could check it. Who knows how that solution was found? But if the answer was yes, there is some way for it to be checked. So any yes-no problem in P is automatically an NP. So I don't need some magical creature to appear with the answer. I can just run the original thing that showed that it was solvable in polynomial time and solve it in polynomial time. So P is a subset of NP. Every P problem is definitely an NP problem. Um but for example, the party planning problem, so that was trying to seat everybody around a table. If I give you a seating plan, you can look and make sure that everybody is okay, that everybody is sat at the table and nobody's sat next to somebody bad. So I'm not saying we could find it quickly, but if the answer is yes, if they can be sat at the table, there's a proof. If the answer's no, it's hard to show what a proof might look like. Factorizing a number into primes, well, that's hard, but if I give you the primes, you can multiply them together again and make sure that you get the right number. So one side is easy, but uh there's a proof. If the answer, so say the I turn it into a yes-no problem by saying, can I factorize this number into exactly two primes? There's a proof, I give you the two primes. That job scheduling problem that I gave you on the slide before, if I give you a schedule for the machines, you can check that it works. So finding it is hard, checking it is easy. So for many problems in NP, we know of no way to find the answer. No way. We can sometimes find it in special cases, we can sometimes find it if it's small, but we don't have a general way to find the answer. But we do have a way to check it if the answer is yes. So yes, you can see the people at table. And so for most of these problems in NP, the way we solve them in practice is by a backtrack search. Which is why I've forced you to imagine all those jobs being assigned to machines. Right. So the million-dollar question. Um, so in the year 2000, to celebrate the millennium, the the Clay Maths Institute, which is the people that um decide on the fields medals and things, chose seven important unsolved problems in mathematics and offered a million-dollar prize for each of them. So they picked seven problems that they thought had the space to shape mathematics for the next millennium, was the idea. Um, and one of them was, is P equal to NP? So rephrased, that's if a solution to a problem is quick to check, then actually is there a clever way of solving the problem? Because there are lots of problems where people have come up with very, very clever algorithms to solve things quickly that look like they might take a long time. But is it always the case that if I can check it quickly, there must be some clever way of doing it, and we just need to think harder. So far, only one of these price problems has been solved. So the Poincaré conjecture got solved in 2003. Um, but otherwise they're they're all available. Um and interestingly, if if P is equal to NP and somebody came up with a practical way of doing it, you can check mathematical proofs quite quickly, as long as they're not too hard. So that would imply that if something could be proved, then you could actually get a computer to generate the proof. So if you could prove P equals NP in some kind of practical way, you could probably get all of those prices. Um now, let me spend most of the rest of the lecture talking about how one might try to start thinking about deciding is p equal to NP? How might you try and prove it? So this slide, some magic occurs. There's no reason for this to be like this, but it is. So we call a problem NP complete. If it's in NP, so there's some way of checking yes answers, and if it could be solved in polynomial time, then every problem in NP could be solved in polynomial time. So a problem's NP complete, if a polynomial time solution to it would mean that P was equal to NP, everything in NP could be solved in polynomial time. Now, this seems like a really stupid definition. This seems like I'm defining something that doesn't exist. But actually, the reason the definition exists is because two people, Stephen Kirk and Leonard Levin, independently proved that there exists an MP complete problem. So they proved it before the word existed, but they showed that there was a problem which, if you could solve it, you could solve every single problem in MP in polynomial time. So Donald Knuth, who's one of the fathers of modern computing and complexity theory, as well as LaTeX, which is a very popular tool amongst mathematicians, uh, in in 1974 he decided to uh have a have a um it was a mail-in, because obviously no email at this point, uh quiz to come up with a good name for uh these problems. He suggested Herculean. Um, and and the winner was NP complete, which he wasn't very happy with because it sounds quite technical and boring. But anyway, the name stuck. And he commented then that he was putting in a huge amount of work and was going to look stupid, because if it turns out that P is equal to NP, then all of these problems are just the same as any other problem. They're just sitting there in NP. But he said that was so unlikely that he was willing to, in addition to any prize money for proving it, offer the winner one live turkey to be delivered upon receipt of a good proof. So anyway, NP complete is due to due to Knuth's um thing, and and and these problems exist. So let me give you a couple of them. Uh, the party planning problem that I opened with, trying to seek people around a table, that's NP complete. If you could solve that in polynomial time, then you'd win the Clay Maths prize and have proved that P was equal to NP. Job scheduling, that was another reason for showing you that one. Um, is NP complete. If you could solve that in polynomial time, then we're done. I haven't put factorizing there, and it's not believed to be NP complete, and I said quantum computers were going to come up again. So Peter Shaw proved in 1994 that so you can't do something on a quantum computer that you can't do on a normal computer, but you can do things much more quickly on quantum computers. You can think of a quantum computer in some sense as simulating running lots and lots and lots of actual computers all at once, depending on how many qubits you manage to make. So we do have a quantum algorithm for factorization, which means if quantum computers get big enough and they don't need to get too much bigger, then we wind up with a polynomial way of factorizing numbers, which means that we wind up with all lots of traditional cryptography being broken. And I'm not just scaremongering here. This is taken from Google's blog. And some of the text is probably too small for you to see. So the headline, I hope you can all see that, says uh quantum frontiers may be closer than they appear. But uh in the small print down below, they they they're talking about how they're moving the security of Android devices and stuff to stand uh quantum attacks, so not to be based on this factorization problem anymore, and they're moving the deadline forward to 2029. So they think that by then or not too long after that, our main way of encrypting messages might break. And that's quite soon. Um so this this is real. Quantum computers will make some problems quicker, but at the moment we don't know a single quantum algorithm to solve an MP complete problem, and there's some evidence that they won't. So factorization is not MP complete, it's hard, but it's not that hard, roughly speaking. So we have quantum algorithms for problems that are hard but not that hard. We don't have any quantum algorithms that make P versus NP irrelevant. Right. This last section, I want to talk about stuff that I actually work on. I've decided I can subject you to a bit of a bit of the things I actually do. Uh so it's symmetry. Uh when I worked in AI, it was all about how to use symmetry to speed up search. So, how can we use symmetry to make things like the job scheduling problem run quicker? So I'm gonna tell you about a problem where there's been fairly recently a big breakthrough. So this is a problem called the graph isomorphism problem. So let me tell you what it is. I've told you what a graph is already. That's the vertices and the edges, the pretty picture that we used for the table. Um, and it asks whether two graphs are in some sense the same. So they might have different names for the dots, different vertex names, but if I could tell you which dot corresponded to what, then it would be the same graph. So I might have drawn them on the board differently. Um so for example, here's one. Hopefully the colours are coming out alright. So here we've got eight, eight vertices, which I've numbered A, B, C, D, G, H, I, J for reasons, who knows? Uh, and there's another one. So that looks quite different, and it's got vertices numbered one up to eight. Um, and the question is, are they basically the same? Could I just like rearrange the lettery one to look like the other one? And in this case, the answer is yes. Uh so the colours haven't come out super different. The colours are meant to be telling you what corresponds to what. So you can see A is a slightly unpleasant looking orangey colour, and that should correspond to one. Or let's make that correspond to one. There's a lot of symmetry, so we have some free choice at the beginning. Um, and A is next to kind of a purpley one, and that's meant to be next to five on the other side. And it's also next to one kind of shade of green and another kind of shade of green, and that's true over on the numbered one as well. So the colours are giving you some kind of way of seeing that these really are the same graph, they just look different. So the graph isomorphism, yes, no, are they the same graph? And this is in NP, because if I tell you, like I just did, if only the pick the colours were making it a bit tough, uh, which letters correspond to which numbers, you could look, as you all were, thank you, and and see that I'm not lying, see that this really is the same graph. So if somebody tells you the answer, you can check it's correct. It's not believed to be MP complete, so we don't think it's one of these hardest problems. Uh we think it's one of the intermediate problems. So the question is, how hard is it? We don't have a polynomial time algorithm for it. Uh people have been trying because it has a surprising number of practical applications, but we also don't think it's MP complete. We think it's somehow in the middle. So, how hard is it? Um and one way we analyze this is by thinking about symmetry. So a symmetry is just a way of shuffling something around so you can't tell you touched it afterwards. So I've drawn us a picture of a graph, and so what can I do with symmetries of this graph? Well, I can swap B and C. If I just like erased the label names and swap them, it would look the same. Uh I can't do anything to D, that has to be fixed. That's the only one with three edges coming out of it, so it's uniquely identified. And I can't do anything to A, because it's the only one with one edge coming out of it, so it's uniquely identified. So this graph has got actually two symmetries. There's swapping B and C, and then there's the do nothing at all symmetry, which we always can't do nothing. Everything has the do nothing. So this one's got two. Um, and in general, symmetries are useful for us, so they often make problems easier. So our fractious family, um, the way I was able to reasonably quickly prove to you that we couldn't see everyone there is because that graph has a lot of symmetries. It's got all the symmetries of a triangle. And so the three corners looked the same, and so I was able to reason quite quickly on the shape of those three corners to show you we couldn't seat everyone. Job scheduling, so this was the machines and giving them tasks. That gets easier if some jobs take the same time, because I don't need to worry which is which. I just have to say, well, I'm giving the 50-minute job, a 50-minute job to machine two. Um, and harder, well, I made all the machines the same so that I could run something on one slide and talk you through it. But if the machines were in some ways not the same, if they were available for different amounts of time or one of them ran more slowly or whatever, that would make the problem harder. So let's talk through easy and hard cases for this graph isomorphism problem. So this is not obvious, but it it turns out that to solve it, it's enough to design an algorithm to find all the symmetries of one graph. So rather than thinking about the pair of graphs, you pick one of them and you find all its symmetries. If you had an algorithm that could do that quickly, you'd have an algorithm that could tell you if they were the same. So there's a graph. You can tell my bad drawings. Uh so that's got ten verses, ten dots. Um, and if you look at that, there's quite a lot of symmetries. So all the dots kind of look the same. So there's there's the outside ones, they've everything's got three neighbors. Um, and then you maybe think the inside ones and the outside ones are different from each other, but if I did some kind of cat's cradle and pulled the inside to the outside, I would again have a pentagon with a star in the middle. So there's a lot of symmetries going on there, and that makes it hard. Whereas this one still got 10 vertices, but you can kind of see that you have to do something to one, two, three. You have to do something to four, five, you have to do something to six, seven, eight, nine, ten. So the problem gets easier if the graph's in more than one bit. There's a technical name for the bits, but I'm not going to bother you. It's just obvious that it's in more, that's in three bits for that second graph. Uh, it gets easier if some of the vertices have different numbers of edges. So you can see with my bottom star type one there that vertex 10 is special. It can't go anywhere else because it's got four edges coming out. So Gene Lux showed in the 80s that it's enough to solve, to solve the graph isomorphism problem. I need to be able to find the symmetries of one graph, and it's enough to solve the problem for when the symmetries form something called a primitive group. Um, and then fairly recently, so if p is not equal to np, we should expect some problems like this that are in NP but aren't NP complete, to take some amount of time that's bigger than polynomial, because they're not in P, but slower than exponential, which is the time that a backtrack search takes. So it should be some kind of intermediate time. And Babai in 2016, so it's not that recent breakthrough now, I guess, but it's it's recent in in terms of the scale of this problem, showed that graph isomorphism can be solved in what's called quasi-polynomial time. So I'm gonna put it up, but I don't really need you to see what it is. Um, the point about quasi-polynomial time is that it is growing quicker than polynomials, growing quicker than any polynomial, but growing slower than any exponential function. So it looks a bit like an exponential. I've got something with a something in the in an exponent there, two to the something, but the thing in the something is a log, so they kind of fight against each other, roughly speaking. Um and then Harold came along a couple of years later and shows that you can in fact take B to be three. So it's a big open question at the moment whether you can make a smaller value of B. There would be quite a lot of renown for managing to get B down to two, for example. If B was one, that turns into a polynomial again. So we're sort of interested in whether it could be close to one, nearly one. Um Right, but I should I should wrap up so we have time for questions. So let me tell you how to win a million dollars. That seems like a fair exchange for your evening. So you first need to decide whether you're going to try and prove that P is equal to NP or P's not equal to NP. I once went to a very big conference with an awful lot of splinter sessions, and somebody with a sense of humour in one of the splinter sessions in a very small room had scheduled back to back a proof that P was equal to NP and a proof that P was not equal to NP. So you need to choose your team and root for it. Um so let's assume that you're gonna go for the P equals to NP1, because that would be more surprising. That would be the thing that really changes the world. Um, all you need to do is find a polynomial time solution to your favourite MP complete problem. So I've shown you a few today, maybe some of them you really like. You can't do it for just any old problem in MP, because that just shows that problem can be solved in polynomial time. You want to show they can all be solved in polynomial time, so you need to do it for an MP complete one. Um as a word of warning, if you were to do that, well that would mean that in particular you can factorize numbers quickly without any need for quantum computers to actually be built. So there are various government security services that would quite like to have a word with you if if you manage to do this. Um, my boss used to joke that if you manage to prove that P was equal to MP, the hardest task would be staying alive to claim the prize. So there are some practical implications I feel I should flag for you here. So maybe contact me first and then we'll take it from there. Not on the internet though. Um yeah. Um the good news, well, all of these MP complete problems are lots of them are very important. So making anything complicated relies on a whole load of scheduling and logistics and so forth type jobs, and all of those would get quicker. So the whole world would see, I mean, never mind what's being discussed now about the implications of AI, this really would affect all these problems that AI can't solve for us at the moment, um, and make everything an awful lot cheaper. And you could solve all of the other clay maths prizes and get another six billion for that. Um, so yeah, transportation, scheduling, and so on are all in MP, and we could do all of them. However, most of us believe that P is not equal to MP. This seems sadly the most likely. A lot of people have spent a lot of time trying to find fast algorithms for these MP complete problems and not found them. The reason we've not managed to prove that P is not equal to NP is that we don't have a good proof technique. Proving that a problem is hard is something that we we just don't have the right methods for somehow. So it needs a brand new Turing scale idea, I think, to make that proof work. Um, so to prove that P is not equal to NP, what you need to show is that some problem in NP has no fast solution. And we don't have a method for doing that. At the moment, we just say, well, I can't solve it quickly, but maybe Sarah could, right? She's just kept it secret. Um so uh yeah, so you you could some problem in NP has no fast solution. You can pick anyone you like. So, for example, uh, I spend some time thinking about graph isomorphism. Um, and so if you like those pictures of graphs, if you can find a way to prove that this is a hard problem for graphs, then you're done. So good luck. Um, and at that, thank you for listening.