In the previous two discussions, we've been talking about what makes a problem hard or easy. And some of the new ideas that have come up because of the way in which we've started in the last half century. Because of the way in which we've started to model minds with machines, we've been able to develop a more nuanced and expressive language about what makes problems difficult or easy. And so we spent the last couple of sessions talking about that, there is much more to say about it. But at least for this session where it's kind of a final session on this topic, but we'll return to the topic as we discuss more about mind to machines. In this particular session, what I'd like to do is talk about how computer scientists think about a certain kind of difficulty of problems. This ultimately is a rather challenging and perhaps technical subject, but for our purposes, I think we can offer and explanation here, we can look at an explanation. And we can explore these ideas without getting too much into the the sort of mathematical depth of the of the subject. So what I'd like to do is described one particular type of difficult problem, and use that to introduce another kind of difficult problem as least as far as computer scientists are concerned. So let's begin with a classic puzzle, I believe it goes back to at least the beginning of the 20th century and the American puzzles, Sam Loyd wrote about this puzzle. I'm not sure if he invented it, but regardless of whether he invented it or not, he popularized it. This is called the Tower of Hanoi puzzle, and you see a picture of it here. There are three pegs, and in this case there are eight discs I believe. So you see a tower of eight discs with each of the discs has a hole in the center. And they've been stacked on the left most peg, and you see that they go from largest disc at the bottom to smallest disc at the top. So what we now want to do, the goal of the puzzle is to transfer these eight discs from the left most peg to the right most peg, and we're going to do that subject to certain rules. The rule is you can only take the top disc off a stack and move it onto another peg. And secondly, and quite important, you can never move a disc to a stack, so that it's resting on the smaller disc than itself, okay? So you gotta transfer these eight discs, you can take a disc off the top of the stack and put it on another peg. But you can't move a disc onto the top of a smaller disc. So if you think about how you might start this particular puzzle, I was considering actually bringing the physical and working it for you. But I decided it would be kind of unwieldy, and if I got the thing wrong on camera, I would be embarrassed beyond measure. So I'm not going to do that, but here's how you might start this particular puzzle. Take the smallest disc off the top of that stack at the left and place it on the middle peg. Now take the second disc of the top of that left most deck because that's now at the top and move it to the right peg. Now as a third move, you could take the small disc which we placed on the center peg and move it to the right peg, and so forth. In other words, what we're going to be doing in order to solve this puzzle is to move the discs one by one from peg to peg subject to the constraint that we can never move a disc onto a smaller disc. Now how hard is this puzzle? This is an interesting question, in one sense, the puzzle is actually quite easy, and here is what I mean. The strategy for the puzzle is easily expressed, and you can find examples, for instance on YouTube where you see people solving versions of the puzzle. So here's the strategy, I've expressed it on this one slide. We want to move a tower of N discs from peg 1 to peg 3, using the center peg as a kind of spare as a place where we can occasionally move discs if we need them, okay? So we want to move a tower of N discs from peg 1 to peg 3, using peg 2 as a spare. Now think about how we could do this, and I'm going to express the solution. And if you consider it, you'll see that this would work. In order to move eight discs from the left peg to the right peg using the second Pegasus there. First, what we're going to do is move seven discs. We're going to solve the puzzle for seven discs, and we're going to move seven discs from peg 1 to peg 2, that is the center peg, using peg 3 as a spare. Now, think about what happens when we do that. We're going to move the top seven discs, we're never going to touch the bottom disc after all, who cares if we're moving only the top seven discs. We don't need the eighth at all, and it'll always be bigger than anything else that we're moving. So for the time being will ignore the eighth discs, the one at the bottom, we'll just work with the top seven. And we'll move those from peg 1 to peg 2, using peg 3 as a spare. Once we've done that, think about what we have at the end of that process. We have one, the bottom eighth disc is still there on the left peg. We have seven discs on the center peg, and the third peg is empty. Now what we do is take the big disc from peg 1 and move it over to peg 3, that's just a simple move. And then we solved the seven disc tower a second time. Moving things from peg 2 to peg 3, using peg 1 as a spare. This is an inherently, the term that computer scientists use for this kind of processes recursive, this a beautifully recursive process. I've expressed it in the abstract way to solve the tower of N disc going from peg 1 to peg 3. First solve the N-1 tower, going from peg 1 to peg 2, move the bottom disc and then solve the N-1 tower again. And you'll see, you could try using this strategy, try it first on a tower. It's trivial on a tower of size one disc. There, you just move the disc from peg 1 to peg 3, for a peg 1 to peg 3 move up two disc. You first move the small discs to Peg 2, the second disc to Peg 3, and then the small disc to Peg 3. So we can solve a puzzle of size one, we can solve a puzzle of size two. Using our knowledge of how to solve a puzzle of size two, we can solve a puzzle of size three, and so forth. So in some sense, the Tower of Hanoi is an easy puzzle. We can express the idea of solving it on one slide. That's all it takes. So is this an easy puzzle? Well, in another respect, this is a very hard puzzle. To solve the tower puzzle with 1 disc, it takes 1 move, just one move. Move the 1 disc from Peg 1 to Peg 3. If you think about what I was saying before, solving the the tower of size two takes 3 moves, solving a tower 3 discs, take 7 moves. You have to do the two solution twice with one additional move in between. Overall, to solve a tower of n discs requires twice the time to solve the n minus 1 disc puzzle plus 1 additional move. So as it turns out, solving a tower of 8 discs requires 255 moves. Solving a tower of 40 discs, and 40 is not a whole lot of discs, it's just a big tower, but you could engineer such a puzzle. Solving that would take a trillion moves. Solving a tower of 60 discs would take a million trillion moves. Now consider what we've just said. Well we've just said is that expressing the idea of the solution is easy. It is easy to say what the solution path would be. But actually enacting that solution, actually implementing it, takes, in fact, exponential time. The time to enact the solution grows as approximately 2 to the n, where n is the number of discs in the original tower. So solving a tower of size 60 takes about a million trillion moves. In other words, we, as human beings, and for that matter, machines, computers, would take a long time to actually print out a solution to the Tower of Hanoi problem. And if the tower starts out with say, 100 discs, we're talking about a problem that would take too long for even the fastest computer to solve in anything like the meaningful time. So even though the problem is easy conceptually, it takes an extraordinary amount of time to implement that solution. And I haven't shown you this, but it doesn't take much to actually see that. We might think, well, if we were more clever, we could come up with a faster solution. Maybe we came up with this easy solution, but, there's a more complex solution to express, but it'll take a shorter time. No, this is the best we can do, this is the best solution you could have. And I haven't shown you that, but that is the truth. So there is no way of improving on the situation that we've got. If you have a tower of size n, it takes approximately 2 to the n moves, even to print out a solution. And that becomes, well, I mean, just impractical at least for either a person or a computer, even the fastest computer. So is this a hard or an easy problem? Well, I don't know how to quite answer that question without sort of going into this sort of detail. In one sense, it's an easy problem. In another sense, it's a very hard problem. Now I mentioned when we were talking about the difficulty of problems earlier, yet a different kind of difficult problem. This is called, you might have heard this term, if you're a computer scientist, you've definitely heard this term. If not, you might have heard this term in the sort of popular culture, the idea of an NP-complete problem. And while I won't go into complete detail, fine detail about what this means, here's what it means in essence. NP stands for non-deterministic polynomial. And a NP-complete problem is one where you can guess a solution quickly in polynomial time. And you can check that you've got a correct solution quickly in polynomial time. But in general, there's no way of actually being sure to find that solution except in exponential time. Now that may seem like a fine detail. Let me show you a very famous example of an NP-complete problem. It's called the Hamiltonian cycle problem. Here's the idea, you have a graph. Think of the graph at the top here in this slide. As it happens, it has 20 vertices and edges between those vertices, okay? The question of whether this graph has a Hamiltonian cycle is whether we could draw a red line starting at one vertex and moving over edges from to vertex to vertex, never visiting the same vertex twice and end up finally at the end back where we started. I've shown a Hamiltonian cycle in the graph below of this graph. So in other words, we have a graph of 20 vertices and the question is does there exist a path that will close on itself, which visits each vertex exactly once and only traverses edges that are in the graph? You might have heard of a variant of this kind of problem under the name of the traveling salesman problem. The traveling salesman problem is one where you have n cities to visit. And you want to visit them each ones and you want to minimize the costs, either in mileage or expenditure, in making a complete tour of all the cities. It's a similar problem, this happens to be a somewhat more, a slightly more abstract problem. Now, in general, if somebody hands you a graph, does it have a Hamiltonian cycle in it? Again, the sort of obvious way to answer a question like that is list all the possible orderings of vertices in the graph. List all possible cycles in the graph and see if any of those cycles that is, list all the possible orderings of, in this case, 20 vertices. See if any of them correspond to valid edges that can move between the vertices. If you find such a thing, the graph has a Hamiltonian cycle. If you can't find such a thing, the graph doesn't have a Hamiltonian cycle. That's a very straightforward Path to a solution. The only problem is that first step. Listing all 20 possible cycles, we don't know when we make a list of all 20 possible, it turns out to be 20 factorial. So if you list all the possible ways of ordering 20 vertices, you have a list whose length is 20 factorial. Many of the elements of that list will not correspond to a cycle because there's no edge between neighboring vertices in that ordering. So you have to actually make a list, it's 20 factorial elements long. And then you have to check each and every one of the elements in that list. Now 20 factorial is a very big number. And as the graph gets bigger and bigger, say I give you a graph of 100 vertices, then my simple solution requires a first step, which involves making a list of 100 factorial elements. Again, a hundred factorial is the kind of number that, it's a beyond astronomical number. There is no way that a computer program could write such a list or go over such a list element by element in anything like meaningful time. So what have we got here? We have a problem that looks superficially like it might be kind of like the Tower of Hanoi problem. In order to solve the problem, we have to do a step that is exponential time. But there is one important difference here and it's illustrated by this two graphs on this slide. Somebody drew this graph a red line that corresponds in fact, to a valid Hamiltonian cycle. It didn't take an exponential time to draw that red line. Unlike the Tower of Hanoi problem, it doesn't take exponential time [COUGH] to actually express a solution. In this case, it took a very short time to guess a solution. And how long does it take to check that solution, not long at all. Just look at the second graph, follow the red line and you'll see, yep, that's a good Hamiltonian cycle. So guessing a solution is brief polynomial time, checking a solution is brief. But as far as anybody knows, and this is an unsolved problem at present. As far as anybody knows, there is no surefire way to find a Hamiltonian cycle that does not need exponential time. NP-complete problems, you might think from this description that I've just given. NP-complete problems are kind of a mathematical oddity, but it turns out they're not. They're all over the place, and they often come up in situations where you have to optimize a solution. They're often in situations of ordering and optimization, and there are many, many np-complete problems that are quite naturally related to the things that we might want to write computer programs to do. So when a computer scientist runs across an NP-complete problem, usually what he or she does is decide that they're not going to be able to solve the problem with certainty. But maybe they can come up with a solution that what is sometimes called satisficing. It'll satisfy the situation and it'll suffice for the current situation. So computer scientists, when they run into NP-complete problems, they often start looking for ways to come up with an approximate solution. NP complete problems are extremely interesting. And they've only been discovered over the last half century or so. Okay, so where does all this leave us at this point? We've now talked about different ways of thinking about difficult problems. First of all, the main thing that the whole point of this discussion has been. There are many ways in which a problem can be hard or easy, some of these have profound implications. Some of them involved the idea that stating a solution would not be difficult, but actually implementing the solution would be difficult. In the case of, we've been talking about the link between machines and mines. In the case of the problems that we looked at earlier, learning one's native language or opening one's eyes, and seeing objects in the world. Those proved to be extremely difficult problems even though in some sense they feel easy for us. We open our eyes and we see objects. But it took millions of years of evolution to get to the point where we would have eyes that were capable of doing that. We learn our native language without direct instruction. But it takes us years to do it. And again, we have a great deal of evolutionary equipment built in that allows us to do this. That gives us the tools to do it. At present, we do not understand entirely the mechanisms either by which we learn our native language, or by which we accomplish the vision task. These proved to be very hard problems, even though they feel easy for us. And as we continue to talk about minds and machines, this sort of gap in the notion of difficulty. Things that are easy for machines but hard for people. Things that seem to be easy for people but are hard to program. These will come to the fore over and over again.
