Transcript
Uh today we're going to in one lecture cover an entire field which is computational complexity. It's sort of uh It meets algorithms in an interesting way which is algorithms is mostly about showing how to solve problems well and showing that you can solve a problem well. Um and computational complexity is more about the lower bound side proving that you can't prove you can't solve a problem very well. You can't find a good algorithm to solve it. Uh we've seen a little bit about lower bounds several lectures ago proving search and sorting lower bounds in the in the bounded uh branching decision tree model.
Um but these are much stronger notions of badness. This is not about n versus n log n or constant versus log n. This is about polynomial versus exponential. Um which has been the sort of bread and butter model of in this class. Polynomial is a good running time and we're always striving for that. Exponential is usually pretty trivial to get. Um and so we're going to talk about some different they're called complexity classes that talk about this issue and different ways to prove hardness. Um this is pretty high level lecture so you're not going to be expected to be able to prove hardness but you'll get a flavor of what it's like and this will segue nicely into other follow-on classes which is we're at pretty much the end of 006.
So natural to talk about what other things you might study. Um one result we'll prove today is that most problems are actually have no algorithm which is kind of shocking. Um and lots of other fun things. So let's get started with uh the notion of P. Uh this is a set of all problems solvable in polynomial time. We talked about what polynomial time means a bunch last lecture. Uh so just recall that polynomial time means polynomial in uh the problem size which I'll denote as n here. The number of words in your input. Okay. Uh so these are the problems that are efficiently solvable. P is set of all of them.
Um and for contrast EXP is the set of all problems solvable in exponential time. Problems solvable in exponential time. Exponential here means uh something like two to the n to the constant. This one reasonable definition of exponential so just the exponentiation of this of polynomial. Uh so as you might expect uh most problem every problem that we've talked about in this class so far can be solved in exponential time rather easily. And algorithms in some sense is about distinguishing these two. Which problems are in P versus are in say EXP minus P. So to formalize this a little bit I'm going to draw a picture.
Which uh is a bit of a simplification of reality but uh for the purposes of this class will suffice and I think is a really helpful way to think about things. Uh which is to have a big axis for a single axis for how hard is your problem? What is the difficulty of solving your problem? Um and I want to be sure to leave So the easiest problems are over here. And each problem is a dot on this axis. Hardest problems are way down the line. And I want to make sure to leave enough space for all the things I care about. So uh P I'm just going to call this segment uh up up front. And then I'm going to have a bigger thing for exponential time.
So this is just to say that P is nested inside EXP. Every problem that can be solved in polynomial time can also be solved in exponential time because polynomial is less than or equal to exponential. These are just upper bounds. EXP Being in EXP means you're somewhere from this line to the left. Being in P means you're somewhere from this line to the left in terms of difficulty. Uh but formally we would write P is contained in EXP as sets. Um in fact they're also known to be different from each other. Um There are problems that can be solved in exponential time that cannot be solved in polynomial time.
For example um I'll put that here. Sure. Uh for example n by n chess is uh in exponential time but not polynomial time. So what is the n by n chess problem? This is I give you an n by n chessboard and I describe to you uh a position. Here's where all the white pieces are. Here's where all the black pieces are. You can have an arbitrary number of queens and bishops and pawns of each color. Uh of course up to n squared of them. They don't overlap each other. And I want to know uh does white win from this position? Let's say it's white to move. Can white win? Um and that problem can be solved in exponential time by exploring the entire tree of all possible games.
Uh but it cannot you can prove that it cannot be solved in polynomial time. So that's a nice example. Uh a more positive example so to speak is negative weight cycle detection. It's literally negative but it's morally positive. Um Negative weight cycle detection is the following problem. I give you a graph a directed graph with weights and I want to know does it have a negative weight cycle? Yes or no? And this problem is in P. Because we saw a polynomial time algorithm for this. You run Bellman-Ford on an augmented graph. Uh so this is an example of a problem we know how to solve. This whole class is full of examples that are that we know how to solve in polynomial time but this is a nice uh non-trivial and succinct one to phrase.
Um it's also an example of a decision problem. A lot of basically all the problems I'll talk about today are decision problems like we talked about last class meaning the answer is just yes or no. Can white win from this position? Yes or no? Um is there a negative weight cycle? Yes or no? Uh Tetris we can also formulate as a problem. Um This is a version of Tetris that we might call perfect information perfect information Tetris. Suppose I give you a Tetris board. Um it has uh you know some garbage left over from your past playing or maybe it started that way and I give you the sequence of n pieces that are going to come and I want to know can I survive this sequence of n pieces?
Can you place each of these pieces as they fall such that you never overflow the the top of the board uh on an n by n board. Uh this problem can be solved in exponential time uh but we don't know whether it can be solved in polynomial time. Uh we will talk about that more in a moment. It's a problem that very likely is not in P but we can't actually prove it yet. All right. Uh so there's one other class I want to define at this point and we'll get to a fourth one also. But R is the class of all problems that can be solved in finite time. R stands for finite. Um R stands for recursive actually.
This is a notion by Church way back in the foundations of computing. Um as we know we need we write recursive algorithms to solve problems. In the beginning that was the only way to do it. Now we have other ways with loops but they're all effectively recursion in the end. Uh so R is all the problems that can be solved in finite time on any computer. Uh so very general. This should include everything we care about, right? Um and it's bigger than EXP. It includes problems that take doubly exponential time or whatever. Uh So I'll draw a region for R. So everything includes P. It includes EXP. Um and so we also have containment but not equal R.
There's of course many classes in between. You could talk about problems that take doubly exponential time and that would have a thing in between here. Or there's also between P and EXP there's a lot of different things. We will talk about one of them. Uh but before we get to the finer side of things let me talk in particular about R. So we have a nice example we being computational uh complexity theory or I guess this is usually just called uh theoretical computer science has a problem. And if you're interested in this you can take uh 604 uh one I think. Uh no that doesn't sound right. That's probability.
It'll come to me. Um we have an explicit problem that is not in R. So, this class has been all about problems that are in P. You have the number? 6045 Thank 6045. Thank you. So close to this this class or it's so close to 6046 which is this natural successor to this class. Uh so 6045 would talk about this. Um So, this class is all about problems that are in P which is very easy, but in fact there are problems way out here beyond R. And here is one such problem. Which we won't prove here today. It takes a whole lecture to prove this. Um given a computer program does it ever halt? Does it ever terminate?
This would be a great thing if we knew how to solve. It's basically an infinite loop detector. If your problem doesn't halt, then it has an infinite loop of some sort and you'd like to tell your user, "Hey, you have a bug in your program." So, this is one part of bug detection and it's impossible. There is no algorithm that always solve that solves all inputs to this problem. Maybe given one program that say has zero lines of code, it could solve that. It says, "Yeah, that one terminates." Uh and maybe you can detect simple kinds of infinite loops. So, there's some inputs, some computer programs that you could detect, but there's no one algorithm that solves all inputs.
So, this is kind of sad news. Uh we call such problems uncomputable. It's just another word for uh being not in R. Okay. Um and next thing I'd like to do is prove to you that most decision problems are uncomputable. Or sketch a proof. So, remember decision problems are problems where the answer is just yes or no. This is a very special kind of problem. Um and even those almost all of them cannot be solved. So, halting is an example of a problem we want uh we can't solve. This whole class is 6006 is about problems we can solve. Uh but today I'm going to show you that actually those are in the minority.
Most problems cannot be computed. This is very strange and also a little depressing. So, we'll talk more about that in a moment. First, let me argue why this is the case. So, we I'm going to be a little informal about what is what exactly is a computer program and what exactly is a decision problem, but roughly uh all I need to do uh the only level of precision I need is just to count how many are there. What is a computer program? Well, it's usually a file. What's a file? It's like a string of characters. What's a character? It's a string of bits. So, a program is just in the end a string of bits, finite string of bits.
We all understand that. Whatever language you define uh in the end you're every program is just a string of bits. Um and a string of bits we can translate into a number. So we can convert between strings of bits and numbers. When I say number, I mean what's usually called a natural number or a non-negative integer. Um this is usually represented by uh bold board black uh bold board uh bold blackboard bold uh at capital N. So, this is just you know, 0 1 2 and so on. Okay? Now, what about decision problems? Decision problem is a specification of what we want to solve. So, we can think of it as saying, "For every input, is the answer yes or no?" That's literally what a decision problem is.
The only question is what is an input? And we've talked about inputs and the size of inputs and and there's lots of different ways to measure them, but in the end we can think of an input as a string of bits also. It's just a file. So, um a decision problem is a function from inputs to yes or no. Um and inputs we're going to say, "Well, that's uh you know, a string of bits which uh we can associate with a number in N." So, here we can start to tie things together. So, in other words, a program is a finite string of bits and a problem is in some sense an infinite string of bits. Uh because there are infinitely many possible inputs and for each of them we specify yes or no.
So, this is basically uh an infinite string of bits. Um so, we can imagine, you know, 0 1 1 0 1 0 0 0 1 1 1 0 infinitely. Um this some for every string of bits we can say, "Okay, if your input is the number zero, here's the answer. No. If your input is uh the number one, then the answer is yes. If your input is the number two, your answer is yes." And so on down this line. Every infinite string of bits corresponds to exactly one decision problem which specifies for every possible input integer which corresponds to string of bits, what is the answer, yes or no? So, this may seem subtle or may seem like not a big deal.
This is a finite string of bits. This is an infinite string of bits, but mathematics has well studied this problem um and infinite strings of bits there are very many of them. Uh infinitely many. It's not surprising. There are also infinitely many integers. So, that's maybe doesn't seem that deep, but um there's a difference in infinitude. Uh programs and integers are countably infinite. Um and infinite strings of bits are what's called uncountable. I think the most intuitive way to see this is an infinite string of bits, if I put a a decimal or binary point in front this encodes a real number between zero and one.
Uh so, this is roughly a real number in 0 1. And when I'm writing approximately equal here, this really goes in both directions, right? Given a decision problem, I can define a string of bits, of course, giving me the answer for all inputs and I can convert that into a real number between zero and one, but also the other direction. If I take any real number, I that is a corresponding decision problem. These are one-to-one uh by bijection between them. Um and the bad news is real numbers are uncountable and natural numbers are countable, which means there's a lot more of these than there are these.
Uh so one may way you might phrase this is uh informally is the number of natural numbers is way smaller than the number of real numbers. And so, from that uh we derive that most problems are unsolvable because every program solves exactly one decision problem. We can also, you know, run a program conceptually on all possible inputs and we will figure out what function it's solving. And if we don't allow random numbers in our program, which I'm not here then every program solves exactly one decision problem. Possibly it's even worse for us because multiple programs probably solve the same decision problem.
They're just they add irrelevant lines of code or they don't do anything different. Or, you know, they run Bellman-Ford versus running Bellman-Ford five times, uh you'll get the same result. Um and that's actually the bad direction for us. We'd like to know whether there is a program that solves every decision problem. Um and because there only this many programs and this many decision problems, it just there aren't enough to go around. So, most uh What's the phrasing? Not nearly enough programs for all problems. Um and so there's no assignment of programs to problems cuz there's just too many problems.
More money, more problems, I guess. Um So, when I first saw this result, I was shocked and dismayed that why are we even doing computer science if most problems can't be solved? Luckily, it seems like most of the problems we care about can be solved. That's what this class is all about. And in fact, even the problems that seem really really hard for us to solve uh like N by N chess where we can prove it takes exponential time, there is an algorithm to solve chess. It's just really slow. Um this is a statement about most problems can't even be solved in finite time, no matter how much time you give them.
Um so it's not all bad. Uh sort of luckily uh most most problems we care about uh are in R. I don't know why. This is sort of a mystery of life, but uh it's good news for it's why we're we keep uh persevering trying to solve problems with algorithms. Is it because when you state problems, the statement tends to be small? Well, I mean this So, the question was what maybe it's just because the short statement problems are easy. But, this is a pretty short statement um and it's hard. Uh I think I I don't have a great reason why. I wish I understood Uh it is a general result that if you have any question about a program itself, then there's no algorithm to solve it.
Basically, any non-trivial question about programs is hard. Uh it's not in R. Uh and I guess if you took and if you imagine taking a random statement of a problem, then maybe this will be in the middle of it with some probability. Uh maybe that's why most, but this is a very strong notion of most. There are so many more real numbers than natural numbers that uh I don't know. All right. Uh I want to add one more class to this picture, which is NP. It nestles in between P and Exp. So, we know that uh P is contained in or equal to NP and NP is contained in or equal to Exp. We don't know whether there's equality here or here.
Probably not, but we can't prove it. Uh but what is this class? Couple of different ways to define it. You might find one way or the other more intuitive. Um they're equivalent, so as long as you understand at least one of them, it's good. NP is just a class of decision problems. So, I defined P and Exp and R arbitrary. They could be problems with any kind of output. But, NP only makes sense for decision problems. And it's going to look almost like the definition of P. Uh problems solvable in polynomial time. We've just restricted to decision problems, but we're going to allow a strange kind of computer or algorithm, which I like to call a lucky algorithm.
And this is going to relate to the notion of guessing that we talked about for the last four lectures in dynamic programming. Uh with dynamic programming, we said, "Oh, there are all these different choices I could make. What's the right choice? I don't know. So, I'd like to make a guess." And what that meant in terms of a real algorithm is we tried all of the possibilities and then took the max or the or or whatever over all those possibilities. Um and so we were But, what we were simulating is something that I call a lucky algorithm, which can make guesses and always makes the right guess. This is a computer that is impossible to buy.
It'd be great if you could buy a computer that's lucky, but we don't know how to build such a computer. Um so, what does this mean? Um So, informally, it means your algorithm can make lucky guesses and it's always makes the right guess. And whereas in DP, we had to try all the options and spend time for all of them, the lucky algorithm only has to spend time on the lucky guess, on the correct guess. More formally, what this is is called a non-deterministic model of computation. And this N is the the N and non-determinism is the N for NP. So, this is non-deterministic polynomial time. Um so, algorithm can make guesses.
And then in the end, um it should output yes or no. So, like say if you're exploring a maze, this algorithm could say, uh should I go left or go right? I'm going to guess whether to go left or go right. And let's say it guesses left, and so then it just goes left, and then it reaches another junction, it says should I go left or right? And I'll say I'll guess, and let's say I guess right this time. And uh in the end, if I I get to some dead end, maybe, and I say no. Or if I get to the destination I'm trying to get to, I say yes. So, that's a non-deterministic algorithm. And what happen What does it mean to run that algorithm?
What does it mean for the guesses to be lucky? Uh here's what it means. These guesses are guaranteed which way you end up going is guaranteed to lead you to a yes if there is one. If possible. So, in my maze analogy, if it is if my destination is reachable from my source, then I'm guaranteed whenever I guess left or right, uh I will choose a path that leads me to my destination. Whereas if the destination is in some disconnected part of the maze and I can't get there, then I don't know what the guesses do. Doesn't really matter because no matter what I do, I'll end up in a dead end and say no.
Okay, that's the that's the model. As long as you have an algorithm that always outputs yes or no uh in polynomial time because we're only talking about polynomial time lucky algorithms. Uh if there's any way to get to a yes, then your machine will magically find it without having to spend any time to make these decisions. So, that's pretty magical computer, and it's not a computer that exists in real life, but it's a computer that's great to program on. It's very powerful. You could solve lots of things with it. Yeah. If you had this magical uh computer that can guess whether it's yes or no, why doesn't it just answer the question?
Right. So, what if we So, a nice check is does this make all problems trivial, all decision problems? Maybe I should say, "Well, I don't know whether the answer to the problem is yes or no, so I'll just guess yes or no." Um this is problematic because uh so, I might say it would guess A or B, and if I choose the A option, I will output yes, and if I choose the B option, I'll output no. In this model, that algorithm will always output yes. Cuz what it's saying is if there's any way to get to a yes answer, I will do that way. And so, such an algorithm that tries to cheat and just guess the whole answer to the problem will actually end up always saying yes, which means it doesn't solve a very interesting problem.
It only solves the the problem which is represented by the bit vector 1 1 1 1 1 1. Uh where all answers are yes. But, good good check. Yeah. Does there have to be a bound on the number of things it has to choose between? Uh yes. Exponential number of Uh Exponential number of choices is okay. Um I I u- I usually like to think of it as you can only guess one bit at a time. Um but that but we're allowed polynomial time. So, if you're actually allowed to guess polynomial number of bits. And at that point, you can guess over an exponential size space, but not more than exponential. Cool. So, it's it's yeah, polynomial time, let's say in the one bit guessing model.
Uh Do I say makes guesses? Let's say let's add binary here. Otherwise, we get some other class, which I don't want. Okay. Uh let's let's do an example of a real example of such an algorithm that's useful, uh which is Tetris. So, I claim Tetris is in NP. Because there is a lucky algorithm, a non-deterministic polynomial time algorithm, that can solve the Tetris game. So, again, you're given a board, you're given some sequence of pieces, uh and you want to know whether you there's some way to place the pieces that lets you survive. Um and so, what I'm going to do is for each piece, I'm going to guess how to place it.
So, for the first piece, I'm going to guess, uh you know, how how far left or right do I move it, then I let it fall one step, maybe I rotate it. Uh I choose a sequence of moves among left, right, down, rotate right, rotate left. Um and all all along the way, I make sure I check is that move valid? If the move is invalid at any point, I just say return no. And then if the piece gets nestled into a good spot, I continue to the next piece. I do the same thing, guess all the possible things I could do to that. Uh again, I only need to guess sort of one bit at a time. Um and I'll only need to do a polynomial number of guesses, like a linear number of guesses for each piece about where it falls in.
So, maybe a quadratic number of guesses overall. Um and then at the end, if I survived, uh oh, I also have to check if the line clears, then I clear the line. Um and if in the end I survive, I return yes. So this is a non-deterministic algorithm. So I would say check the rules of the game. And if we survive return yes. And if at any point we violate the rules, for example, we go off the top of the board we return no. So this is an algorithm that sometimes returns no and sometimes returns yes, depending on what choices you make. And this model guarantees if there's any way to get to a yes, it will find it.
If I swapped these answers if I returned yes when I violated the rules and returned no if I survived, this would be an uninteresting algorithm because it's very easy to lose in Tetris. The hard part is to survive. The if I say is there any way to play the game in in such a way that I violate the rules, then of course the answer is yes. Uh you can just stack pieces and go off the top. Uh there's an asymmetry in this definition of yes versus no, right? We We always finds yes answers if possible. Um it doesn't always find no answers if possible. So it's very important the the way that I wrote these questions.
It's important that I define Tetris as the problem of can I survive? The problem of uh can I not survive? Is it impossible to survive? That's a different question. That problem is not in NP, probably. Okay. So slight subtlety there, yes versus no. Let me give you the other definition of NP. So if this one's confusing, which although I prefer this definition uh most people do not. Uh so this is confusing, let's do the other definition. So other definition is that NP is a set of decision problems um that can be checked in polynomial time. Um Well, this actually came up in the last lecture where we talked about subset sum.
I said, here's a bunch of integers, here's a target integer, and I can prove to you that this integer can be represented as a sum of numbers from my subset of numbers from my set because here they are. I gave you this plus this plus this equals the target sum. Um and so that is a solution in some sense that can be checked for a yes example. If I can represent my number as a subset sum of a given set, it's easy for me to prove that to you. And you can check it just by adding up the numbers and checking that each number was in the set. Um whereas no instances we had I had an example of a target sum that could not be reached and the only reason I knew that is cuz I had brute-forced the thing.
Um and there's no succinct way to prove to you that that number can't be represented. Uh similar thing with Tetris. Um What I would say is So this is version one. Version two for Tetris is that um a certificate for a yes uh input of Tetris is um a sequence of moves for the pieces. Okay, if it's possible to survive in Tetris, I can prove it to you. I can just play the game and show you that I survived. No answers, I don't know. It's hard to prove to you that I can't survive a given sequence of pieces, but yes answers are easy. I just show you Here's Here's the sequence of button presses I'll do for this piece, then for this piece, then for this piece.
Notice it's exactly the same thing that I guessed in the beginning of this algorithm. Um and then I did some other work to implement the rules. And similarly, if I gave you a certificate, which is the things that I wanted to guess of how to play the game, I can check the certificate by just implementing the rules of Tetris and seeing whether I survived. And if you violate the rules at any point, you say no. And if you survive, you return yes. That's what's called a verification algorithm. So let me formalize this notion. Uh Given a problem input plus a certificate like that one over there um there is a polynomial time So this is yet another definition.
This is what I mean by this definition of NP. Uh verification algorithm that satisfies two properties. One is for every yes input, so every input where the answer is yes to the problem um there exists a certificate uh such that the verifier says yes. So this is saying it's possible to prove to me that an answer is yes because if there's if you ever have an input that the answer happens to be yes you can prove it to me by giving me a certificate. There's always some certificate that proves the answer is yes because the verifier, which runs in regular polynomial time, this is a regular old-fashioned down-to-earth verification algorithm, polynomial time in our usual sense um it will say yes.
And furthermore, the yes answers from the verifier are actually meaningful because if I ever give it a no input it always says no. No matter what certificate I give it. So this should really formalize what all this means. It's equivalent to the previous definition. Um this is saying that proofs exist for yes instances and this is saying that proofs don't exist for no instances, meaning there are no false proofs. So if the verifier ever outputs yes, you know that the answer to your problem is yes. Um but if it outputs no, you're not sure. Maybe you got the certificate wrong cuz we only know there's some certificate where the verifier will say yes or maybe it was a no input and then it didn't matter what certificate you used.
But it's nice because it says on say Tetris, if I give you the sequence of pieces, it's very easy to write down a verifier which just implements the rules of Tetris. Um and so then you can at least check whether a solution is valid in the yes case. In the no case we don't have anything useful. So NP is a a structure, some additional structure about the yes inputs in your problem. And a lot of decision problems are in NP. A lot of the problems that we care about uh can be phrased as an NP problem. As long as it's a decision problem, usually answering yes or no uh is provable. Uh like subset sum, like Tetris, these are all problems where if the answer is yes, I can give you a convincing proof why.
Um and it turns out a lot of So a lot of problems fall into this NP setting. And so we have some tools for talking about uh problems being uh hard with respect to NP. Let me first talk a little bit about um P does not equal NP uh {question mark} um A lot of people conjecture that P does not equal NP. It's sort of a standard conjecture in theoretical computer science, but we don't know how to prove whether P equals NP or or is not equal NP. Um and so in this picture, I've drawn the hypothesis, which is that NP is a strictly bigger region than P is. Uh but we don't actually know whether there are problems in this region.
We don't know whether there are problems in this region between NP and EXP. We conjecture there are problems here and there are problems here. Uh there's definitely problems here or problems here, but we don't know which one. Cuz we know P does not equal EXP, but we don't know whether P equals NP. We don't know whether NP equals EXP. If you could prove that P does not equal NP or just prove it, uh you would win a million dollars, which is not that much money these days, but uh you would be famous to for the rest of time if you could ever prove this. Uh every year there's usually a crackpot proof that doesn't work out.
Um it's Some Some of them go to me. Uh please don't send them. Um and anyway, the it's it's a very hard problem. It is sort of the core problem of theoretical computer science, how to prove P does not equal NP. But for the most part, we just assume it. Uh Now, what does this conjecture mean? It essentially means The way I like to say it is you cannot engineer luck. Cuz NP problems are problems you can solve by lucky algorithms. P are problems you can solve by regular old algorithms. And so if P equaled NP, it means luck luck doesn't buy you anything, which seems weird. Like if I can magically make these super powerful guesses, uh then I can solve the problem that that's NP.
That seems super powerful, way more powerful than regular algorithms where we have to actually brute force and try all the choices. Um and so it seems seems pretty solid that P does not equal NP. That's my my Of course, we don't know how to prove it. Another phrasing is that it's harder to come up with proofs than it is to check them. From a mathematical perspective, this is equivalent to P does not equal NP. So that's why you should believe it. Um now uh let's go over here. The next notion is NP-hardness. So in particular, I want to claim This is a theorem that exists in the literature. That if P does not equal NP then Tetris is not in P.
So I said right here, Tetris is in X but we don't know whether it's in P. But in fact, we conjecture it's not in P because we conjecture that P does not equal NP. If you could prove this conjecture, and there's a lot of theorems that are conditioned assuming P does not equal NP, then we get some nice results like Tetris cannot be solved in polynomial time. Cannot figure out whether to win whether I can win a Tetris game in polynomial time in the input size. Why? Um this is a consequence of another theorem, which is that Tetris is NP-hard. I'm going to define NP-hard informally first and then I'll define it slightly more formally in a second.
Uh but this means uh roughly that Tetris is as hard as all problems in NP. So let me draw this in the picture. So NP-hard is this part. Oop. Did I leave myself enough room? Maybe not. Well, we'll squeeze it in. There's another region here for X-hard. Uh so your problem being in NP was a positive result. It says you're no more difficult than this line. You're either at this position or it's to the left. Being in P was also a positive statement. It says you're here or to the left. Being in P is better than being in NP cuz this is a subset of that. Um NP-hard is a lower bound. It says you are at this point this level of difficulty the or to the right.
Um and so it goes from here off to infinity in difficulty. And X-hard says you're at least as hard as the right extent of the X uh set uh or you're harder than that in a sense that we'll formalize in a moment. Um and this place right here, as you might imagine, is kind of interesting. It's exactly where NP meets NP-hard. This thing is called NP-complete. You probably have heard about NP-completeness, famous notion, and this is what it means. Um it is the problems that are in NP, so they have a lucky algorithm that solves them, they can be verified, their certificates that can be verified, and they are NP-hard.
So they're in NP and they are the hardest among problems in NP. Now they're not the hardest problem. There are actually many problems right here at this single level of difficulty called NP-complete. Um among them is Tetris. There are many others which I will list in a moment. Uh so that is NP-completeness. So um because these problems are the hardest problems in NP if there's any problems here in between in NP minus P, then these must be among them. And so if you assume that P does not equal NP, as most people do, then you know that all problems at this rightmost extreme of NP, the hardest of the problems in NP, they must not be in P.
And that's why I can say if P does not equal NP, Tetris is not in P. And also any NP-complete problem is not in P. Okay. What does as hard as mean? This is our good friend uh reductions. We've talked about reductions a lot in this class. Reductions are the easy way to use algorithms. You just take your problem and we reduce it to a problem you already know how to solve. You take uh the input to some problem that you want to solve and you convert it into an input to some other problem like single source shortest paths or something like that that you already have an algorithm for solving. So if you have an algorithm that solves problem B you can convert that into a solution for B.
And a reduction should also tell me how to given a solution to B, how to convert it back into a solution for A. And when I say solution here, I actually mean certificate from over there. Uh so how like So if I um yeah. Okay. So if I have So reduction consists of these two pieces. How to convert an input at A to an input for B and given a solution to B, how to convert it to a solution to A. Let me give you some examples of reductions you've already seen. You've seen a lot of them. Um if I have unweighted shortest paths on the left unweighted uh single source shortest paths, I can reduce that to weighted shortest paths.
How? Set all the weights to one. So here I'm given a graph without weights. If I set all the weights to one, that turns it into an input for weighted string shortest paths. So if you didn't know how to solve this, you could solve it by converting it. If you've already written say a Dijkstra algorithm, you could apply it to solve unweighted single source shortest paths. Now we know a faster way to solve this, but you know, it's only a log factor faster. And here we're talking about polynomial versus exponential. Okay. So this is a valid reduction. It's not the most interesting one from an algorithmic standpoint, but it is an algorithm.
Uh another one we have uh we've seen is if you have integer weights on the left you can convert that to unweighted on the right by uh positive integer weights by subdividing each edge of weight W into W edges of no weight. Um so that that's maybe a little bit less efficient. It depends how what the sum of the weights are. Um another version that we've seen is longest path in a graph. We can weighted path uh we can reduce to shortest path in a graph weighted by negating all the weights. We did this in some of the dynamic programming things. Like oh, longest path in a DAG, we can convert that into shortest path in a DAG just by negating all the weights.
So these are all examples of converting one problem to another. Usually you convert from uh for algorithms, you convert from a problem you want to solve into a problem that you already know how to solve. But it turns out the same tool reductions can be used to prove negative results, too. Uh and in this case, we're going to reduce from a problem that we think cannot be solved and reduce it to the problem that we're interested in solving. Okay. So uh let me write more precisely what this means. If you can find a reduction like this, it means that solving A is at least as easy as solving B. Right?
Because I can solve A in particular by converting it into B, solving B, and then converting it back to a solution to A. So in other words, if I can solve B, I can solve A, which is I can phrase informally as A is at least as easy as B. And now using uh grammar or contrapositive, whatever, uh this is the same thing as saying that B is at least as hard as A. And this is what I mean by at least as hard as. So this is my definition of at least as hard in this notion of NP-hardness. Okay. So what NP-hard means is that I'm at least as hard as all problems in NP. And so what that means is every problem in NP can be reduced to Tetris.
Which is kind of funny. Um but in particular, that means that if there's an algorithm for Tetris, there's an algorithm for all problems in NP. And so that's actually the contrapositive of this statement. So it's saying if there's a polynomial If I take the contrapositive of this, this is saying if there's a polynomial time algorithm for Tetris then P equals NP. There's a polynomial time algorithm for every problem in NP. The way we prove that is by reductions. We take an arbitrary problem in NP and we reduce it to Tetris. Luckily, that's not as hard as it sounds because it's already been done once.
There is already a reduction from NP to uh from all problems in NP to singular problems out there. The NP-complete problem, which I guess is Turing machine non-deterministic it's basically simulating lucky algorithms. So it's kind of a not very interesting problem. But from that problem, if you can reduce it to any other problem, you know that problem is NP-hard as well. And so briefly I want to show you some examples of that. Here. So I want to start out with a problem that I'm just going to assume is NP-complete. And it's called three-partition. It's one way to phrase it is I give you a bunch of integers.
I have it written down over here. Also the board. I give you n integers and I'd like to divide them up into n over three groups of size three such that each group of size three has the same sum. As it's written there on the board. So you can also think of this as the following problem. I give you a bunch of rectangles that are side length or a bunch of sticks, let's say, of varying lengths. And I want to group them up like on the right diagram. So in groups of three such that the total length of each group is exactly the same. Okay, this is just a problem and just believe for now that it is NP-complete.
I won't prove that. But I I'd like you to what I'd like to show you is a reduction from this problem to another problem, solving jigsaw puzzles. So you might think jigsaw puzzles are really easy. And especially easy if I lose the projector. But in fact, if you have a jigsaw puzzle where some of the matches are ambiguous, if there's multiple pieces that could fit against a given tab or pocket. Then I claim I can represent this three-partition problem by building little sticks like here. So if I want to represent a stick of length AI, I'm just going to build an AI I didn't mention they're all integers and they're polynomial sized integers.
I'm going to represent that by a bunch by AI different pieces here. And the red tabs and pockets are designed to be unique global to the puzzle like a regular jigsaw puzzle. Given this piece on the left and this tab on the right, there's a unique pocket there's a piece with a unique pocket that fits perfectly into that piece. So this this joining is forced. And also this joining is forced. But the blue tabs and pockets are different. They're all the same. They're all identical. And so if I build this frame using the you know red unique uh assignments and I build these rectangles. If I want to pack these rectangles into this rectangle, that's exactly the three-partition problem with some details that I didn't fill in.
But it turns out you'd be forced to group these into groups of size three something like this. Varying lengths but Okay, so that's an example of a reduction. If you believe the three-partition is NP-hard, this proves to you that jigsaw puzzles are NP-hard. Something you may not have known. Every time you solve a jigsaw puzzle, you can feel good about yourself now, especially if it has ambiguous mates. Next is Tetris. So here is a reduction from the same three-partition problem, which is one of my favorite problems, to Tetris. It starts out with this strange board. It has a bunch of um columns here where I could put pieces.
So I'm not allowed to put pieces in these dark regions. They all have height T. T is the target sum that we want all of the numbers to all of the triples of numbers to add up to. And there's n over three of these slots where I can try to put pieces. And it's because of this thing over on the right, there's no way to clear lines in this game. And now to represent a single number AI, I'm going to give you this sequence of pieces. It starts with an L piece and then it has AI repetitions of this pattern and then it ends with these two pieces. And so what ends up happening is that uh this is in the intended solution.
You first place an L at the bottom of one of these buckets and then you repeat this pattern in this nice way and it fills up AI roughly height of this bucket. And then at the end you have to put the I here. Uh And what this what this ends up guaranteeing is that all of these pieces go into a single bucket. It's you can check, it's tedious. But if you tried to put some of these pieces in one bucket and other pieces in a different bucket, you would lose some space and then you would die. So if you want to survive, you have to put all these pieces into one bucket. And so again, we're just stacking rectangles.
We're putting a whole bunch of rectangles in one pocket and then a bunch of rectangles in another pocket. We can switch back and forth however we want. But the only way to win, it turns out, is if you get all of those rectangles to add up to exactly the right height, then you get a picture like this. If you don't get a picture like this, you can prove you end up dying. Then I'll give you a bunch of L's. Then I'll finally give you this T which clears some lines. Then I'll give you most satisfying Tetris game ever. I'll give you a ton of I's and you get Tetris Tetris Tetris and you clear the entire board.
And so if you can solve the three-partition problem, you can clear the board and win the game and be best Tetris player ever. And if there is no solution to three-partition, you're guaranteed to lose. And so this proves Tetris is NP-hard. Cool. So what else do I want to say? Briefly. I think that's the main main idea. So another example. So this spot is called X completeness. And this includes problems such as n by n chess. So we know that chess requires exponential time because in fact it's among the hardest problems in exponential time. But most common are the that's somehow because of the two-player nature of the game.
Most common are NP-complete problems and we have a bunch of example NP-complete problems I'll just briefly mention here. So we saw the subset sum problem which we had a polynomial time algorithm for. Sorry, a pseudo polynomial time algorithm for last class. In fact has no polynomial time algorithm assuming P equals NP. So pseudo poly is the best you can hope for for subset sum. There's a related notion called weekly NP-hardness which I won't get into here. Three-partition is one we saw. We saw some reductions to other problems. So these are all NP-complete. Longest common subsequence is another dynamic programming problem we saw with two sequences.
I mentioned you could solve it for three or four or any constant number. But if I give you n sequences each of length n, that problem is NP-hard. NP-complete. Longest simple path in a graph. We know how to solve longest path, you just solve shortest path with negative weights. But longest simple path where you don't repeat vertices, that's NP-complete. Relatedly, one of the most famous NP-complete problems is traveling salesman problem. The short finding the shortest path that visits all vertices in a given graph. So instead of just going from A to B, I want to visit all the vertices in the graph.
A lot of these problems I'm phrasing as optimization problems. But when I say NP-complete, I actually mean a decision version of the problem. For example, with this one, the decision question is is the shortest path that visits all vertices in a graph less than or equal to a given value X. If you can solve this, then by binary search you can solve the overall weight. Three-coloring a graph is hard even though two-coloring a graph is polynomial. Three-coloring is NP-complete. Assigning three colors to the vertices so that no adjacent vertices have the same color. Finding the largest clique in a given graph which would be useful for analyzing social networks, whatever.
This is a fun one for me as a geometer. If you're in a three-dimensional world, which I am, and I want to find the shortest path from here to there that doesn't collide with any obstacles like this desk and all the chairs and so on. In 3D, this problem if you can fly. So if you're a drone flying among all these obstacles and you want to find the shortest path from A to B, this is NP-complete. Quite surprising. In two dimensions it's polynomial. You can reduce it to graph shortest path. But in 3D it's NP-hard. This is a formula problem that comes up a lot. Given a Boolean formula with and or or not, can you ever make it true if it has some variables that are not assigned?
And some more fun examples are Minesweeper or Sudoku. Basically any paper and pencil puzzle you've ever played. There's probably a paper out there proving that it's NP-complete. And on the video game side, Super Mario Brothers is NP-hard. Legend of Zelda is NP-hard. Pokemon is NP-hard. These problems are actually all a little bit harder than NP in a different class called PSPACE which I won't go into. But if you're interested in this stuff, there is a whole class devoted to it which has online video lectures. So you can watch them whenever you want. Called 6892 that gives a bunch of especially fun examples of NP-hardness and other types of hardness proofs from a sort of algorithms perspective for lots of games and puzzles you you might care about.
And that's it.