00:00:02,097 --> 00:00:03,930 SAMMY: Well, thanks for watching my seminar. My name is Sammy Mara. I am a senior studying computer science here at Harvard. And P versus NP is what I'm going to be talking about. It is the greatest unsolved problem in computer science, and maybe all of math, I think. And it's something that has fascinated me for a while. So I think it's a natural extension of the CS50, and I hope you learn something from it. We'll go into some of the details, as well as the big picture of what is P versus NP. And yeah. So let's get started here. This is just to show that P versus NP is sort of like a relevant problem, and it shows up in pop culture. This is Homer Simpson in some matrix void thing, and you can see P equals NP floating in the background there. And then in Futurama-- I guess that's also a Matt Groening production-- P and NP in separate books, sort of implying that P is not equal to NP. 00:01:02,880 --> 00:01:05,610 Really, the question is whether or not P is equal to NP, and we'll get into what that means in just a second. But if you're watching this and you thinking hey, I want to solve P versus NP for my final project, got some bad news. It's probably not the best idea. Don't want to discourage you, but a lot of really, really famous, smart people, much smarter than me, have tried to solve this problem for a long time. And its applications are very far-reaching, and I think we can learn a lot from it, but the problem may not be solved for a long time. 00:01:39,750 --> 00:01:45,450 And yeah, why should we care about the theory of computer science? And in CS50, you learn a lot about the running time of algorithms. And we talk a lot about how algorithms work and what are the best ways to solve certain problems. But theory of computer science sort of goes into how can we extrapolate from there? And what are the fundamental things about algorithms that make them similar to one another and different from one another, as well as how to model the computer in its simplest form? That's something that Alan Turing did, way back when, and he became famous for that. Everyone is-- I mean, not everyone, but a lot of people are familiar with like Turing machines. That's sort of his theoretical model of a computer. And yeah. It helps us solve problems and use solutions from one problem to solve other problems, so it's pretty profound. And yeah. So I have a little more motivation in answering this question of P versus NP. And I still haven't really told you what it is. But solving this problem would essentially help us with questions like are algorithms invented or discovered? Is there some fast algorithm for solving Sudoku that we just haven't discovered yet? Or did it just exist in the ether and we have discovered it yet? Or are we just like too dumb to discover it, but like definitely exists? Or does it just not exist at all? And yeah, this question is-- if that wasn't motivation enough, it's a million dollar question in the sense that the Clay Institute-- It's one of Clay Institute's Millennium Prize problems, which means there is $1 million for whoever person can solve it and prove it, one way or the other. Because what do computer scientists love more than computers? Yeah, money. And I'm hoping that a CS50 student will be the one to solve this problem one day. So I hope you can-- So what is the question of P versus NP? And it's really, are problem that are easy to check also easy to solve? And that's sort of a very, very, very high-level thought-- way to think about it. But what is this word easy mean in this context? What does it mean to check a problem? What does it mean to solve a problem? Hoping to go into all of that in just a minute. And hopefully that will become clear. 00:04:09,010 --> 00:04:13,410 So yeah, this problem in particular has a long history. Back in the mid 1960s, when computers were still the size of cabinets and small houses, people were still trying to find algorithms to solve basically all the world's problems, like factoring and the Traveling Salesman Problem, and determining if a number is prime, and problems like these. But some problems they had slow algorithms for, they were able to solve them, but it just took a long time. And for some algorithms, like find the greatest common divisor and sorting, we have fast algorithms like merge sort. That's, worst case, running a prime of, I think, n log n. I'm a CI. I should know that. So things like that just have fast algorithms. But for some problems, we just have no no fast solution. And then in 1965, people came up with a solution to the discrete Fourier transform, and suddenly, that was in the fast category. And for things like determining if a number is prime, that took until 2002 for someone to find an algorithm to do that, until it could be in this fast category. And I'll explain what a fast algorithm is versus a slow algorithm in just a second. But for a lot of these algorithms, there were just no-- for a lot of these problems, there were just no such algorithms that were able to be solved quickly. And it didn't seem like we would ever find a fast solution to these problem. And so that is really the question, is will we ever find fast solutions to these problems? And actually, the answer is very unclear. Although, I think one of the most important moments for this problem was a theorem that Steven Cook of MIT and Leonid Levin came up with. And it basically said that a lot of problems that we face in computer science are all connected by some sort of core difficulty. And what that means is that if you could solve-- if you could have a fast solution to one algorithm or one problem, you could actually use the same algorithm to solve very different, seemingly different problem. And that was a good way to categorize these problems, and we learned a lot from that about complexity and general complexity theory being the fields of categorizing these problems. So I think that was a really important moment. Yeah. So let's go into a little more detail here about what P is, what is NP, why are they fighting, and so forth. But at the very base of it, P and NP are sets of problem. Normally in math, we think about sets of numbers or sets of elements or sets of words or whatever. But now we're talking about sets of problems. And the way these problems are defined is whether or not they have these fast algorithms. So some problems, like the problem in P have known fast algorithms. And some problems that are in NP are at least able to be checked quickly. And definitely, if a problem is P, it is in NP because if you can solve a problem very quickly, it's also easy to check it because you just solve it again. And that will all become clear, hopefully, in the next few slides. But yeah, so let's talk first a little more in-depth about what is P? The set polynomial time, which is basically the set of problems where there exists a polynomial time algorithm that generates a solution. That might be a little bit confusing at first. But in CS50, hopefully, you learned a little bit about big O notation or worst case algorithm runtime. And what this means is that these are the types of problem that can be solved in a polynomial amount of time. That could be like 3n to the 5th plus 5, where n is the size of the problem by some definition. So these problems include finding the GCD of two numbers. We have a fast algorithm for that. It's been known for lots of-- many, many years due to Euclid. Excuse me. And you can see this is the Euclidean algorithm right there. And it just is very deterministic. You just put in input, and you can slowly boil down the problem into a solution. Linear programming is basically like a set of equations. Let's not worry about that too much right now, but that's another problem that is well known to be in P. And determining if a number is prime, that actually-- as I mentioned earlier, that result wasn't found until 2002. But that is also in the P family of problems. And multiplication, as you probably all know, the algorithm for multiplying two numbers. You just sort of go through one by one. And that's, at least-- if you multiply every digit by every other digit, that's sort of like n squared. And then you add them up. So it's at most n cubed. But crucially, these albums-- excuse me-- algorithms aren't like 2 to the n or something exponential. So that's what makes them in this category of P. Yes. And yeah, so let's move on a little bit to the set NP, which stands for nondeterministic polynomial-time time, which is sort of like a way of saying, well, they have polynomial algorithms to solve them, but they're nondeterministic, which means you just sort of have to guess or use an infinite number of computers before you can solve them in a polynomial amount of time. But the way these are defined formally-- and before, we talked about problems that can be solved quickly. Now, we're talking about problems that can be checked quickly. And what that means is it's a set of decision problems-- and I'll explain what that means in just a second-- for which there exists a polynomial algorithm to check if a solution is correct. So before, we were saying I'm giving you a problem; tell me a solution and some definition of the solution. And now I'm saying here's a problem and a solution, and I want you to check the solution. So does that checking take a polynomial amount of time? And so these problems are-- I guess problems included in this set are like Sudoku because if I give you a Sudoku board and said this is solved, how fast would it be for you to check if it was solved? It actually wouldn't take you that long. You'd probably just go through every row, column, and nine by-- excuse me-- three by three square to check. And that's what n cubed. But crucially, it's not something like 9 to the n, which would be an exponential amount of time. 00:10:57,800 --> 00:11:00,800 And in other problems like factoring, it's easy to check if a factor or a factorization is correct. You just multiply the numbers, and then you can see if that factorization is correct. A much harder problem to factor the numbers, by the way. And Traveling Sales problem's an example of famous NP problem where you're given a graph with vertices and edges. And we'll get into a little more about graphs in just a second because those turn out to be really relevant to NP problems and thinking about them. But again, multiplication-- I thought we just said that was a P problem. Well, if something's in P, it's also in NP because if I said, well, what's 51 times 3? If I said 51 times 3 is 153, well, how would you know? You'd probably just check it yourself and multiply yourself. And of course, that's, as we described, a P algorithm. So that has a P algorithm to check whether or not my solution is correct. That's how you know it's in NP. So we've talked about P. We've talked about NP. So now, we have a couple examples here, and maybe give you a better grasp of how to think about different problems. So sorting a list, is that in P or NP? Well, we talked about sorting and the running time of those in CS50. Hopefully, you know that that's, for a lot of sorts, that's n log n or n squared, I think, for a quick sort. But those all have polynomial time algorithms, so those would be in P, also in NP. Multiplication, we just described P algorithm, right? It's something like n cubed. And then given a set of vertices and edges, is the graph connected? Is that P or NP? Well, you just start at a point, and you traverse until you have seen all the edges. If you haven't seen-- excuse me, all the points. If you haven't seen all of the vertices, then you know it is not well connected. And another example would be a Rubik's cube. First of all, is that in NP? That is, is there a way to check if the Rubik's cube is solved? Well, yeah. It's pretty easy. You just check if all the faces are solved. But is it in P? Is there a polynomial time algorithm to actually solve the Rubik's cube? That is actually a little harder to think about, but it turns out it is actually-- computers can do that fairly fast. And what about the best move in chess? Is that in NP? Well, if I told you that this was the best move in chess, could you check that it's the best move in chess? Probably not. I think you'd have to go through a more calculation to determine if that was the best move. And that problem, actually, is not in NP or P. That's in its own class called exponential time, where it takes exponential time to even check if a solution is correct. And then there's problems like-- a classic NP problem is like the subset sum problem, which means given a set of integers, say, I'm asking do they sum to negative-- is there a subset that sums to negative 1? And in this case, you could just look at it. And if I gave you-- sorry, if I gave you a subset and then said these sub to minus 1, it would be really easy to check. You just sum them up, and they sum to minus 1. But solving that problem actually isn't very easy. And there's some sort of exponential checking that you have to do to determine if there is such a subset. And if you think about how many subsets there are, 2 to the n subsets, I believe, where there's n members of a set. So you have to check a lot, and that's a good indicator that it is not in P. But in this case, it is, as we showed, in NP because it's easy to check. 00:14:45,050 --> 00:14:49,930 So I was talking to you before about NP completeness. And this is sort of one of the most important concepts to understand when talking about P versus NP problem. Basically, what this means-- and this is related to the Cook-Levin theorem that was talking about earlier. It essentially says that all of these problems-- and this is an example of a bunch of NP problems-- they're all sort of connected. Where, if you have a solution, say, to the graph coloring problem, you can use it to form a solution to the clique cover problem or to the hitting set problem or to the yada, yada-- you can basically form one solution into the other. And that's really powerful because if someone one day finds a polynomial time algorithm to do one of these problems, that means they can find a polynomial time algorithm to do all of these problems because they're all sort of related, and they can be converted to one another very quickly. 00:15:42,190 --> 00:15:44,580 And I sort of glossed over detail there, which is how fast can these algorithms solutions be converted to one another? And that has to do with reduction. And I just want to talk about this for a second because this is one of the more core concepts that is involved when proving these things. And this is actually what computer scientists have to do when they talk about-- are these problems NP complete? Are these problems related by some core difficulty? And what it means is basically a reduction is a polynomial time algorithm that converts a solution from one problem to the solution of another problem. And I'm going to be talking a little bit about three particular computer science related problems, which are the independents set problem, the vertex cover problem, and the clique problem. Independent set problem has to do with-- basically, given a graph like the one I'm showing in the slide, are there are a set of k vertices, such that there are no 2 of those vertices are touching or related by an edge? The vertex cover problem means can you give me a minimum set of vertices that covers all the edges? That is, that all of the edges are-- excuse me. All of the vertices are touching every one of the edges in the graph. And then the clique problem-- I don't know if it's "click" or "kleek." Some people say "kleek." But it's related to the colloquial sense of the word clique, which is like a friend group. Is there a friend group, essentially, in this graph where every single person in the graph, every person represented by a vertex, is connected to every single other vertex in the clique? And in this case, you can see there is actually a 5 clique in the bottom left of these 5 vertexes are all connected to each other. And so that makes them what's called a 5 clique. So these are the three problems that I'm going to go into in detail just a second. And I'm going to show you that they're actually all sort of the same problem. And solving one can actually give you a solution to another. So let's take the example of this graph. Again, graphs generally is a set of vertices, excuse me, and edges connecting them. And this is an example of an independent set. So how do we get this? If I just said to you give me 4 of these points, such that no 2 of them are related by an edge, then this would be the solution. Great. So how long does that take? Well, if it were a big graph, it would have taken some exponential amount of time. There's no polynomial time algorithm to do that. But if we are able to get a solution, we can use it to solve some other problems. And in this case, we can use the independent set to solve the vertex cover problem. How do we do that? Well, we just consider all of the vertexes in the compliment. So basically, all of the vertex that weren't in the independent set, consider those to be in the vertex cover. And these have the property that every single vertex is related to every other edge. I don't know if I'm explaining that correctly. Every vertex in the vertex cover is touching every single edge. And in this case, you can hopefully see that. And so we just created, out of nothingness, a solution to vertex cover from a solution to independent set. And we can even take it one step further with clique. The way you do this is you consider the points an independent set, or the graph of independent set, and then take the complement of the edges, which means that every edge that doesn't exist already, you fill it in. And every edge that did exist, you get rid of it. And what you're left with is this graph. And all of the points that were originally an independent set are now a clique-- in this case, a 4 clique-- for this new graph. So it took a long time to create a solution to independent set, an exponential amount of time. But now that we have that, we're able to create solutions to other similar problems. And it turns out there's a wide range of problems that are related, even problems not really seemingly related to graphs at all. So this is what's called this the satisfiability problem. Given a clause, or basically a logic clause, where each of these variables-- I don't you can see where I'm pointing in the video, but these are all basically variables that are either true or false. And so what the satisfiability question is asking is whether or not this clause has a truth assignment. That is, there exists an a and b, such that this all becomes true. And for those who don't know, these little downwards carrots are or's. And the upward carrots are ands. And the little-- I don't what you call it. The little sideways dashes are nots, so the opposite. If it's true, it's false. If it's false, it's true. So the question is does this have a truth assignment? And maybe you can just eyeball it and say, well, actually, if A is true, and B is false, and C is true, then this statement can be true. And that indeed, that is the case. So how do we reduce-- how do we take that solution and turn it into a solution to, say, the vertex cover problem? In this case, all we have to do is create this graph. And there is an algorithm to create this graph. And what it does is you basically-- I don't know if you can see this, but every clause of the original statement up here turns into 2 variables at the bottom of this graph. So you have AB turning into AB down here, not A, not B, not C turning into these 3 points down here. And then not ABC turning into not ABC. And then finally, you just take every a and its complement up here. Now, let's say we have the solution, A, not BECAUSE. Then basically, you want to color these, A not BC on the top line. And then you want to connect every single element to itself. So not B goes to not B. B goes to B. A goes to A. Not C to not C. And that's that. The point is that basically-- oh, did I miss something? 00:22:12,210 --> 00:22:17,570 So then you basically color these based on-- there is a relationship. I'm actually blanking on it right now. But basically, there's a way to color these. And basically when you color the A, not BC, and then B, not A, not CBA on the bottom, that creates a vertex cover. And so you've used a solution, you've used an algorithm, that creates a solution from the satisfiability into the vertex cover that is actually very powerful. And that's what's called a reduction. I know that was a little bit involved. I'm still trying to figure out how these are related. But basically, A, not BC-- yeah, so I think what it is, is if it's A is colored here, then you color all the not A's in this bottom graph. And if not B is colored here, then you colored all the B's in this bottom graph. And again, if you color C here, then the not C is colored here. And I think using that algorithm, you can create a solution to vertex cover. Why is this the solution a vertex cover? So this is one thing I didn't mention, is that all of the colored things are covering every single edge. That is, every single blue node here is connected to every single edge in this graph. Also, as we discussed before, vertex cover is related to independent set in the compliment. So if you consider all the white nodes in this graph, they form a independent set where no 2 of the white nodes are touching. So now we've created solutions to two of these problems from a seemingly completely unrelated problem, which is the satisfiability problem. And that's actually really powerful when considering these type of NP problems. Sorry, that was a little bit wordy. Hopefully, you got something out of that's. Let's go on to more fun things like the Turing machine. Way more fun. Of course, this is due to Alan Turing, the man who needs no introduction. But basically, this was his theoretical model of a computer in its simplest form, which is basically just something that runs an algorithm. I think this is sort of-- this image helps to see that. It's a machine that runs an algorithm on an infinite tape of 1s and 0s. And that is a computer at its simplest form. And Alan Turing saying that that mathematical functions on numbers can be just as well computed by a Turing machine, that was basically what was concluded in what's called the Church-Turing thesis. And I like to think of this as basically a reduction of a computer to its simplest abilities, the ability to read from memory, the ability to write from memory. And that's really all you need. You could interpret this Turing machine of just 1s and 0s as like blocks of 8 bits. And then you could have bytes, say. And then you can work in letters, as opposed to just 1s and 0s. And so I think reduction is just a concept that comes up a lot in computer science, so it's good to know. And not just in the sense of problems to problems, but also, for example, computers and things that solve those problems. 00:25:22,550 --> 00:25:25,974 It's worth noting, there are also other theoretical ways of thinking about computers. Today, we have quantum computers, which is just another theoretical model of a computer. And that has different ramifications for the P versus NP problem. And the problem kind of breaks down in that sense. But at least for Turing's notion of computers, this is what we'll talk about. 00:25:47,770 --> 00:25:51,720 Yeah, so what is the resolution to this problem? Is P NP? Is P not NP? Are these problems-- is there a problem that's not in NP but-- excuse me-- in NP but definitely not in P? And the answer is pretty unclear. But there's a lot of smart people, not like me, but smarter than me, who think that there's definitely not a solution. Because people have spent a lot of time thinking about this question. And for a lot of these NP complete problems, they just can't find efficient algorithms. I think this comic sums that up nicely. 00:26:23,290 --> 00:26:28,120 So it's very much seems like P is not NP, so I hate to break your all hearts. But a lot of people think that P is not NP. There are some people who think P is NP. And then there are the people who have different conceptions of the problem like, well, it's a badly worded problem. Any of the definitions of P and NP are unrelated in their definitions. So there's a lot of conceptions, but most computer scientists think it is a well-formed question and that P is not equal to NP. 00:26:56,800 --> 00:27:01,720 So how would one go about proving this question of the relatedness of algorithms solving problems. And it turns out, it's just not easy because the way we define these sets is by the existence of algorithms, right? So to prove P is NP actually is "easy" because all you have to do is find one polynomial time algorithm for a NP complete problem. And then immediately, the whole class collapses into P. That is, because if you had a polynomial time algorithm to solve an NP complete problem, you could solve all of the other NP complete problems because we told you that they're all related by some core completeness. And then to prove P is not equal to NP is much harder, in the sense that you have to prove that an algorithm doesn't exist. And that is actually kind of difficult to solve because in the past, we've just invented new algorithms, and it just took enough time before someone was like, oh, well we can do it this way. And we don't have proof that an algorithm doesn't exist in P. It's only until we just find an algorithm in P that we can be sure that that wasn't-- excuse me-- was in NP and not in P. So that is inherently not an easy task. And I think that's why that makes this problem so fascinating and so frustrating for a lot of smart people. I think one of the most interesting ways to think about this problem is in terms of what if P did equal NP? And I think this is like a counter-- or excuse me, like the-- I don't know what the word is-- contradictive argument, where you say, well, what if P did equal NP? And if P did equal NP, then the world would be a lot different. If P was NP, then every problem that would be easy to check would also be easy to solve. What does that mean? Actually, I don't know. I didn't realize this when I first started to research this problem, but RSA encryption, which is like basically the basis of a lot of our modern encryption, would be very easy to crack because it's based on factoring. It's based on factoring large, large numbers. And if those numbers were easy to factor, they would be very easy to basically decrypt a lot of messages that are passed online and things like that. But of course, we're relying on the fact that P is not equal to NP, and that there is no algorithm that exists currently to do that. Another ramification via artificial intelligence systems would be making huge leaps almost overnight because a proof to P equals NP would also tell us something fundamental about solving certain problems that AI people solve. I don't want to go into details too much there. But another ramification, for example, would be that the economy would be perfectly efficient, which means that if there were any arbitrage between two different-- well, arbitrage works by taking advantage of the different price discrepancies in a graph. And if those are easy to detect-- that is, if there were a polynomial time algorithm to detect them, then it would immediately be easy to find these arbitrage opportunities, which is sort of a very bad thing. And then, one other thing would be-- a lot of people say that proving things, or mathematical proofs, is such an NP problem because, well, it's easy to check if a proof is correct. You just follow the logic. It's much harder and it's a creative task to actually create a proof. And so we might be able to write programs that make mathematical proofs if P did equal NP, which would just like be crazy, and that would just make the whole world explode. The world would be fundamentally different than the way we currently think it is. And a little more philosophy here, which is one of the fun things I like to think about, is proving things-- well we talked about it. It is sort of like an NP problem because you can just follow the logic, and it's easy to check. Is comedy an NP problem? If I tell a joke and you laugh at it, then it's really easy to check that that was a funny joke. Much harder task to write a funny joke. I know, because I do stand up, and enough people have sat in silence at my jokes. I know it's a very hard thing to do. Music. Appreciation of music. Is it easy thing to check? Well, yeah. If you just listen to something, you can kind of intuitively tell that that is a nice sound. But it is actually much different much more difficult to create music, to create good music. These are all sort of philosophical arguments. These aren't really-- the actual definitions of P versus NP that we're exploring have a much more well-defined relationship to Turing machines and what are called languages. But when you think very high level, the ramifications are endless for any sort of creative pursuit. And Scott Aaronson of MIT once said that, "If P equaled NP, then the world would be a profoundly different place than we normally assume it to be. There would be no special value in creative leaps. There would be no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who can appreciate a symphony would be Mozart, and everyone who could follow a step-by-step argument would be Gauss." And I think that tells you something about the crazy ramifications of a proof that P did equal to NP. 00:32:52,780 --> 00:32:53,989 Yeah, so why should you care? Hopefully, you're sitting here and being like, well, that's great, but I have a final product to do. And this doesn't really help at all. I don't think many of you are going to be doing theoretical proofs or anything like that or talking about theory. Although, I think you should. We talk in CS50 about running time of different algorithms. And that is very relevant because there could be a faster way to do the problems that you're thinking about. You just don't know yet. And that's why theoretical computer scientists research the fastest way to do certain things. And that's why reductions have shown us-- reductions from NP complete problems have shown us that like if a problem exists of this problem, a problem that you're trying to solve might actually have already been solved. Or another other thing is that, well, if you assume P doesn't equal to NP, something you're trying to do might not be that easy to do. And if that wasn't motivation again for why you should care, well, it's a million dollar question, right? And there's nothing that computer scientists like more than computers except for money, right? So I think that should be motivation enough for you to be interested in the P versus NP problem. It is something that is really interesting to me. I know I took you through the weeds a little bit with the actual reductions, but I hope that was interesting. And that's really what computer scientists do when they think about these types of problems, is reduce problems to another and sort of relate these algorithms. And so I think that's about all I have. But I hope you enjoy. Here are some links. Just the P versus NP page is a collection of the status and history of the problem. And this is just a video I really like. It explains all these things very well. That's all I have. I hope that was enjoyable for you. And for everyone out there enjoying it on YouTube, I guess, I hope you could take something away from this. And yeah, P versus NP. It's pretty cool.