. Today, we're going to talk about intractability in our last lecture. this is an appropriate topic to close the course on because it really lays out for us some of the big challenges of the future. most people are taking this course because they're going to want to be involved with algorithms, algorithms in the future. and this topic really helps us lay out what's ahead. As an introduction, we'll review some very, very basic questions about computation. Some of you may be familiar with this subject area others may not be at all. So, it will just be a brief review in either case. But some of the concepts are relatively easy to understand and so, and they lay a good background for starting with computation with intractability. We need to think about computation itself first. There are these kinds of questions that came up actually about the same time or even before computers actually were invented or came into use. Now, what is a general purpose computer? What does that mean? are there limits on the power of digital computers? That's another interesting question. Are there limits on the power of any machine that we can build? this kind of question with the outgrowth of similar questions on mathematics that was posed by David Hilbert in the beginning of the twentieth century. and there were some very profound thinking going around Hilbert's questions, and later, around the questions on computers that initially were related, but then took on a new life of their own. To take a look at the idea of what these mathematicians were thinking about in the middle of the twentieth century that we call the simple model of computation that we looked at when we were working with the KnuthMorrisPratt algorithm. so what we did was we imagined a, a machine, an abstract machine called a discrete finite automaton or an FSA, a finite state automaton. that is a very simple machine where we imagine that it's got a tape that has the input. that's just a long strip that's divided into cells. It's got a finite alph, alphabet of symbols and it had a tape head that could read one symbol from one cell of the, of the tape. And then, based on what it saw, it would move to a different state. It would move one cell at a time, read up all the tape, all the input, and if it got to the right state, we'd say it'd accept it. That's what we did with KnuthMorrisPratt was we imagined this machine and then we built a program that now constructed a table which just said what to do, which state to go to for each symbol on the each possible symbol on the tape for each state. and then that was a way that we got this problem solved. in, a natural question arises when mathematicians and theoretical computer scientists first started taking a look at abstract models of computation like this is, can you make them more powerful, is there a more powerful model of computation than DFA? Well, it didn't, it didn't take long to realize, of course the, there's a more powerful model. And actually, the progress was almost incremental. You can think of it as being almost incremental where you just add a little bit of power to the DFA that we can show, that makes that more powerful but, but what's the limit? and actually the, the limit was proposed very early on by Turing in here at Princeton in the 1930s. it's a universal model of computation where just like the DFA, we imagine a machine that has a finite set of states. but instead of just reading the tape, it can write on the tape as well and it can move in both directions. so, it, it can store intermediate results on the tape. but, other than that, it's very similar to what we imagined for the FSA. And now the question is, is there a more powerful model of computation than this one? and the remarkable fact is that Turing answered this question in the 1930s. Actually, he did the work just before he got here to Princeton, and then finished the paper. He said, no, there's no more powerful model of computation. In fact, many of hailed this as the most important scientific result of the twentieth century. because it, it tells us really wha t we need to know about the power of the machines that we build. so with Church, who was Turing's adviser here at Princeton, the we have the thesis that there's no more powerful machine. Turing machines can compute any function that can be computed by a physically harnessable process of the natural world. Now, this is not a mathematical theorem because it's a statement about the natural world. It's, it's not something that you can prove from basic principles. but it is something that you can falsify, you can run an experiment that shows it not to be true. And the whole idea behind this thesis and, and behind Turing's proof about abstract models of computation is that and we've seen it many, many times. So, we can use simulation to prove model equivalence. So, we wrote a Java program to simulate a discrete finite automaton, and that means that Java's at least as powerful as that. you can write people have shown you can write Turing machines that simulate the operation of, of store program computers, like the one's that we use. Or if you use an iPhone and you're running an app that's written for the Android or vice versa, that simulation that proves models that are equivalent, demonstrates that models are equivalent. And that's been an extremely effective way for us to understand that different computers have similar capabilities. That, you know, you're not going to compute more by build, building some new machine. so these had profound implications. And, it's, it's really amazing that Turing came up with this so long ago really before computers came into use at all. and it means that we don't have to try to invent a more powerful machine, or, or language and it really enables rigorous study of the computation that we can expect to do in the natural world. so that's the basis for the theory of computation. And it's, it's related to the study of algorithms. but, because it gives us a simple and universal model of computation. But we haven't talked about efficiency. how long does it take to simulate an Android to s imulate an iPhone and so forth? So, what about cost? what about time? That's been our focus when developing algorithms. and what we want to think about next is how to deal with that cost. but first, I just want to lay out the evidence that we have for the Church-Turing thesis. That is, it's been eight, eight decades and nobody's found a machine that can compete more than we've been computing with the machines that we have. And the other thing that was really convincing to the mathematicians in the mid-20th century is that people tried all different types of models of computation. Church was working on something called the un-typed lambda calculus, which actually is the basis for modern programming languages. And there are other mathematicians working on recursive function theory and grammars and other things. And eventually, essentially, they were all able to use these languages to express the formalism of another one, and then therefore, prove them to be all equivalent. And that comes in through to the modern day with all programming languages. You can write a simulator or a compiler for one programming language and another, or a different random access machines, simple machines, like cellular automaton. and even computing using biological operations on DNA. or quantum computers that you may have heard about. all of these things have turned out to be equivalent. So, there's a, a lot of confidence that the Church-Turing thesis holds. but what about efficiency? So, this is a similar starting point for the study of algorithms. What algorithms are useful in practice? so in order to know what the, what useful we're going to consider time and we're going to say that it's an algorithm that it's not just that it's in theory, would, would complete the problem is that it actually would solve the problem in the time that we have available. and just to set a dividing line, it a, a, a clear bright line it, it, we're going to say is that we'll consider it to be useful in practice or efficient. If it's running time is guaran teed to be bounded by some polynomial in the size of the input for all inputs. and for the purpose of this theory, we don't even care of what the exponent is, could be n to the 100th. now you might argue that's not a very useful dividing line but it is a useful starting point. and as you'll see, even the starting point has told us a great deal about the kinds of algorithms useful in practice. and, this was, this work was started in the 50s.' also, here at Princeton. and many, many people looked at models for trying to understand what, what this meant. the dividing line is between polynomial as, as I've said, and exponential. Exponential is a two the, the n-th power of some constant of greater than one to the n-th power. And we'll talk about that in just a second. so sorting is useful. It, so anytime it's bounded by a polynomial or, but here's another one which is finding the best traveling salesperson tour on endpoints. if you're going to try all possible tours that algorithm is not useful in practice because n factorial is not bounded by a polynomial in n. Its running time actually grows like n to the n-th. so, this is a useful starting point for our theory because it's very broad and robust. and if we can put some algorithms in the class with sorting and other algorithms in the class with traveling salesperson using brute, brute force search, that's going to be useful. It'll tell us which algorithms we want to use. We definitely can use the, think about using the first but we can't think about using the second. and, and actually, unlike turing machines, where we wouldn't actually kinda play turing machine to solve a practical problem. in this theory, it's often the case that the polynomial time algorithms will scale to help us solve large problems because the constants usually tend to be small. but the, the key is the idea of exponential growth and I just want to be sure to convince everybody that it's not about, when it comes to exponential growth, it's not about the technology. That is a dividing line th at no matter how fast your computer is, you can't be running an exponential algorithm and expect to be solving a large problem, in just a thought experiment to reconvince everybody of that. So let's suppose that, imagine that we had a huge, giant, parallel computing devices. This thing is so big that it's got as many processes, processors as there are electrons in the universe. So, we have a supercomputer on every electron and we'll put the most powerful super computer we can imagine today on every electron in the universe. and then, we'll also run each processor for the lifetime, estimated lifetime of the universe. so, how big a problem can we solve? Well, it's estimated there's ten to the 79th electrons in the universe and supercomputers. Nowadays, maybe can do ten to the thirteenth instructions per second. and you can quibble about these numbers and make it ten to the twentieth if you want. it's estimated the age of the universe in seconds is ten to the seventeenth. And if you don't like that, make it ten to the thirtieth. You multiply all those numbers together you're going to get a, a relatively small number to say a thousand factorial. ten to the seventeenth times ten to the thirteenth times ten to the 79th is only ten to the 109th or something. Whereas a thousand factorial is way bigger than ten to the 1000th. It's more like 1000 to the 1000th, alright? So, there's no way that you can imagine solving a thousand city TSP problems using that brute force algorithm. You can let your computer run but it's not going to finish. technology is out of the picture when we have exponential growth. So, that's why it's so important to know algorithms are going to require exponential time and which ones aren't. in this theory it would seem. let's at least get that classification done. so which problems can we solve in practice? We're just going to say that the polynomial time algorithms are the ones that we can solve in practice that guaranteed polynomial time performance. so that brings us right to the question, which problems have polynomial time algorithms? and unfortunately, it's not so easy to know that. get stuck right away on trying to do that classification, and that's what today's lecture is all about. so, this is a similar bird's eye view to when we introduced the classifying algorithms when we're talking about reduction. And reduction's a very important tool in this theory as well. So, what we're going to say is a problem is intractable if you can't guarantee that you can solve it in polynomial time. so what we want to do is prove that the problem's intractable. there have been a couple of problems that have been proven to require exponential time. but they are a bit, artificial. well, so here's one. Given a constant size program, does it halt, and in most case that's or here's another one. Given an N by N checkers board, can the first player force a win if you have the force capture rule? Well, N by N checkers board for large N is again, that's a, certainly a toward problem. But for the many real problems that we actually would write this, like to solve, unfortunately, there's been very few successes in proving that a problem is intractable. So even though it would seem that you would be able to be able to separate problems that can guarantee problems polynomial times solutions from problems that require exponential time for some input, there's been very little success in proving that. but that's an introduction in a motivation for the theory of intractability.