Okay, so now we are going to look at the final topic in our course and which is going to be the topic that concerns the study of decision problems, languages, and complexity classes. This is by the way of introduction to a broad field of study called the theory of computation which is very closely related to algorithms. This study is the inherent difficulty of solving problems. Inherent difficulty of solving problems. What you will learn from this, is certain problems are inherently hard. We know why. Certain problems are inherently easy to solve on a modern computer, and certain problems, we do not know. We do not know whether these problems are inherently difficult, or it's the lack of human ingenuity and imagination that prevents us from finding good solutions. In this lecture, I'm going to lay some foundation for thinking about problems, the concept of decision problems languages, and introduce the notion of complexity classes culminating with looking at two very important complexity classes, P and NP. I will explain what these are in the course of this lecture. Throughout this course, we have studied algorithms for problems. We have studied algorithms to solve problems. Somehow, we've never formally defined the notion of what a problem means. We're going to try and do that, try and capture this notion of what is a problem. Let's take an example of an algorithm. We are given an array A of n elements, and we are asked, does element e belong to the array A? We are designing a box, and let's call this problem belongs to array problem. We are interested in a box, belongs to array, that's the name of the box. In goes in an array A, in goes in and element e, and out comes an answer yes or no. Yes if e belongs to A, no, if e does not belong to A. An algorithm is used to fill this box in. An algorithm is a procedural way of implementing this box. Such a box which has a yes-no answer is called a decision problem. It's a problem whose answer is always yes or no. As an example, let's take examples of decision problems. Given a graph G and two vertices, s and t, which belongs to the graph, does there exist a path from s to t? Let's call this the path exists problem. This is an example of a problem with a yes-no answer. Here we are given a graph. We are given two vertices in the graph. We want to know, yes, if s is connected to t, no, if s is not connected to t. This is an example of another decision problem. Let me give you one more decision problem. For example, given a number, we can ask if the number is prime. Given a number, and typically you have to write down the number in binary representation of the number. Given a number n in binary as an example, I gave you an example, is n prime. This is an example that takes in an input, a number n encoded in binary. Yes if it's prime, no if it's not prime. Decision problems are problems with yes-no answer. But then the question is, are all problems decision problems? Clearly not. What are examples of problems that are not decision problems? Well, for example, sorting is not a decision problem. Given an array A, your goal is to find a sorted array A. That's clearly not a decision problem. Now, what are the other examples of not a decision problem? We looked at knapsack. If you take knapsack, you have a bunch of items whose weights are known, whose value is known. You have a weight limit w. Then the question is, choose items of maximum value such that total weight is less than equal to w. This is another example of something that's not a decision problem. The answer is not yes or no. The answer is a list of items. If you have knapsack, you have a list of items, you have their value, then the answer is a subset of items maybe that maximizes the value such that, oh, by the way, you have to give me that weight limit capital W, the answer is a subset of items. These are examples of clearly not decision problems. What about another example of something that is not a decision problem? Let's say factoring a number. In factoring a number, you are given a number n and you are asked to give me the smallest factor, let's say P of n. You are given a number n, which is let's say even the product of two prime factors, PQ, and you want to give the smaller of the two prime factors. That's the result. This is called factor. Here, the result is not a decision problem. Many problems are clearly not decision problems, but for many problems, you can have a decision version of the problem. What does it mean to have a decision version? Let's take an example. Let's start with factoring a number. Instead of calling factor, let me call a new decision version factor. Let me put a question mark. Let me give you a number n to factor and let me give you an index I. I'm asking the question. I'm to frame everything as a question. Is the [inaudible] bit of the smallest factor Pa one? Let's call this the decision version. Instead of saying that, given a number n, let's say 35, which is seven cross five, I'm asking, give me a number, n equals 35, give me a bit index I, let's say two. I'm asking, is the second bit of the smaller factor a one? If I ask this kind of question, I've changed the problem. But interestingly enough, if I can solve the decision problem, I can use it as a subroutine to quickly extract the factor. Do you think that's possible? Can I use the decision version? If I gave you the number n and I gave you the index I, and I can tell you whether that index is one or a zero, do you think by repeatedly calling the decision version, can you quickly figure out the factor? Yes, of course. All you need to do is start from i equals 1, i equals zero to i equals log n. In fact, half log n really. This is going to be the number of bits of P will have to be less than equal to the number of bits of n divided by two. P cannot have more than half the number of bits of n. Therefore, if number of bits of n is roughly log n, so i going from zero to log n, repeatedly done this and you can get the answer, so you can extract the factor. What about the knapsack problem? Recall the original knapsack problem gave you a list of items, gave you a total rate, and asked you to find a selection of maximum value. Find a selection. Here, the idea was in the knapsack, find a selection of maximum value. Instead of that, the decision version will become, is there a selection of value greater than or equal to some value limit v? So instead of saying find a selection of maximum value, say, is there a selection of value greater than equal to v? If I know that the answer for this, I can use binary search to actually narrow down on the maximum value selection. All I need to do is instead of answering this question, find the selectional maximum value, I can instead ask the decision version, which always has a yes or no answer. Is there a selection of value that's at least capital V? Just like I gave a capital W limit on the total weight, let me ask, is there at least capital V that I can get? What about sorting? It's a little bit lame, but I can always ask the decision problem. Is element e the i-th element in the sorted array? This is not very convincing. Sorting does not have a good decision version, so not all problems have a nice decision version, but I claim that most problems that we are interested in have a nice decision version. Most of what we are going to be concerned with in this lecture are going to be decision problems, problems with yes-no answer. So decision problems. Why are decision problems nicer to study? Well, there are two answers to it. Number 1 is the size of the answer is just one bit, so things like computing a big answer, so suppose you had one problem where the answer was very big and another problem where the size of the answer was very small, then comparing them in terms of the size of the inputs is not that useful because the size of the answer is going to matter. For example, problems like compute the first thousand digits of Pi, 10,000 digits of Pi are not problems for which we care to analyze the complexity. We want to standardize the size of the answer, and the easiest standardization is to have a one bit answer, a yes or no, and that's just one bit that comes out of the problem. That is one way of thinking about it. It makes for a useful way of thinking about problems. All right. The second useful thing is that we can make a connection between problems and languages. Unfortunately, I'm not going to have a lot of time in this class to make this connection. This is typically a connection that's made in a proper theory of computation class, and if you ever get to take one, I highly recommend. These connections are made, but it's an optional class. It's typically a theoretical class, a mathematical class, and that's kind of optional. We will make this connection in terms of languages, but let me just explain very quickly. Whenever you have a decision problem, you define a set of, also decision problem has two answers, yes or no, define set of all inputs, which gives us the yes answer. We call this the language associated with the problem. Why is it called a language? It's called a language because this set is going to be a set of all encoding. Let me give you an example. Let us take the language prime equals the set of all binary numbers, n, such that n is a prime number. This language is going to have 10, 11, 101. This is just 2, 3, 5, 111, 7, and so on. This is going to be the language. This language can be thought of as a subset of binary strings made of zeros and ones. Now, let us call the path language, and this is a slightly more difficult language. It's the set of all graphs with source node, destination node such that G encodes a graph, S is a node in the graph, T is a node in the graph, and S is connected to T in the graph. This is the language of all graphs which are connected to path. Once again, we encode it as a binary string. We encode all this information as a binary string. That is going to be a way in which I view all problems as in terms of the sets of inputs which gives us the yes or answer, and this is called the language associated with the problem. Using this notion of language, we can start to standardize a lot of what we mean by a problem. How do you define a problem? Well, a problem is defined by a language. A language is defined by choosing certain strings, which have some meaning. This has some meaning, but I don't have to really tell you what the meaning is. This could be an encoding of a number, encoding of a graph, and so on. These are called languages. Starting from the early 20th century, people started studying languages in terms of their, how do you build algorithms? An algorithm can be formally defined as a box which, given an input string, tells me if x belongs to a language, so L. This is called algorithm that recognizes language L. Now, what kind of a machine runs this algorithm? That is very, very important. I'm going to skip through a ton of details and just tell you that there is a very universal class of machines called Turing Machines. Now, what's a Turing Machine? A Turing Machine, which was by the way, invented by the scientist Alan Turing, very, very fascinating person, who is very rightly called the father of modern computer science. Alan Turing came up with this model of a computer. In Turing's model of a computer, there is basically some kind of a logic, I'm not going to describe it too much, which is going to read from a tape, and on this tape is written a string. It's going to at some point either say yes or no. It's going to stop at some point and say yes or no. When it reads a character in the string, it can move the tape head either to the left or to the right, and internally shift to a new state. I am glossing over a lot of details here just to get you on the same page in terms of what's a model of a computer. It turns out that this very, very simple model of a computer, and what does this logic look like? This logic looks like this. You have some states as zero. If you read the string one, you could go into state one, and then you tell the machine to move left. If I read a string zero, maybe I stay in state zero, tell the head to move right. Then certain states are stop states. You can have stop states, stop and accept, and say, "Yes." Certain states you can stop and say, "No." This is how the logic is built. Each arrow says, "If I am in S1 and I read a zero on the tape, then let me move right and move to S2. If I am in S2 and I read a zero on tape, let me move left and stay there. If I am in S2 and I read a one, let me move right." These are going to be the transitions. This is a very, very simple model of a computer. This is a super simple model of a computer, but interestingly enough, everything that our machines can do, our RAM based computers can do, can be captured by a Turing machine. Likewise, everything that's captured by a Turing machine can be captured by the RAM based computing model that we are used to. Likewise, it turns out that any physically realizable model, so people came up with lots of physical models of computation. They came up with RAM based machines, the kind that runs our programs these days. Well, those were shown to be equivalent to a Turing machine in terms of computing power. They came up with something called Lambda calculus, which influences the design of lots of programming languages, and this was by someone called Alonzo Church, and that was shown to be equivalent to a Turing machine. Something called a Post machine, and that was shown to be equivalent to a Turing machine. Marvin Minsky, a very famous computer scientists came up with something called a Minsky machine that was turned to be equivalent to a Turing machine. Quantum computers, which we will briefly look at next week, were turned out to be equivalent to a Turing machine. It turns out that there is a thesis which is fundamental to computer science, and this is called the Church-Turing thesis. It says that Turing machines are a universal model of computation, which means that any physical device that can carry out any form of computation, it's taken to be equivalent to a Turing machine. In other words, this is a thesis, this is not a theorem. This is just saying that it's a article of belief and we believe firmly, due to lack of evidence to the contrary, we believe in this thesis, and this thesis says that any physically realizable computing device is equivalent in its computing power in terms of what it can compute to the model of computation that Turing proposed, that's called a Turing machine. This is central to computing. What it means is that Turing machines came out as some model of computation. Now, if you go back to all the boxes we wrote down, prime, path connected in a graph, kth bit of factor, all the decision problems we wrote down, what we are looking for is an algorithm. Algorithms are meant to be run on Turing machines. Obviously, in this course, we don't teach you algorithms on Turing machines because they are completely impractical to write Turing machines. But we taught you a lot of algorithms using pseudocode that was supposed to run on these RAM-based machines. That was for a reason because these RAM-based machines are being shown to be equivalent to Turing machines separately. We never have to worry about whether our pseudocode is physically realizable because we know it is physically realizable because it can be realized on a RAM-based machine and the RAM-based machine is equivalent to a Turing machine. Again, we did not define these things because it gets a little bit tedious at this stage of your education. So what am I getting to? What I'm getting to is there is a first boundary between problems that can be solved on any computer as we believe computers are defined, so on any computer problems that can be solved, and outside, these are problems that cannot be solved on a computer. We get to our first shocking realization. Not everything that we care about has an algorithm. There are certain problems outside. There are, of course, many problems here that have an algorithm. Everything we've studied in this class belongs to be inside this box. Example, problems that can be solved using a DFS, whether there exists a cycle in a graph, whether a number is a prime number, the bit of the factor, the decision version of knapsack. These have seen plenty of problems inside this box. But interestingly enough, there are problems that lie outside this red box that cannot be solved on a computer. These kinds of problems have a name, they're called undecidable problems. Likewise, problems that are inside are called decidable problems. There is decidable problems in this world and there are undecidable problems. Undecidable problem means that no Turing machine can solve this problem. Therefore, by the equivalence of Turing machines, RAM machines, and so on, the computers that we have today that we are physically capable of constructing cannot solve these problems. What are examples of undecidable problems? Examples of undecidable problems. There are plenty of examples [inaudible]. The first example that Turing [inaudible] is known as the halting problem. Let us say that I give you a program [inaudible] and I want you to build a smart IDE that says, does this program have an infinite loop or not? Know if program does not have infinite loop. This is called the halting problem. I want to build a smart compiler that solves the halting problem. What is the halting problem? It says that given a program, so suppose I give you the text file of the program you wrote, let's say the program you wrote for your programming assignment, dfs.py, so given a Python program. I want to give this compiler to take in this Python program and say yes if the Python program has an infinite loop, no if it does not have an infinite loop. This is called the halting problem. Turns out, you cannot solve the halting problem. There is no algorithm is capable of solving this problem, which is very, very, very surprising, but it is a very, very powerful result. You cannot solve this problem. Now, what about problems of the kind we could care about that are undecidable? There are examples. For example, the diophantine equation problem, also known as Hilbert's tenth problem. Now, suppose I have a polynomial equation, let's say x squared minus y squared equals, I don't know, 5. I want to know, are there two squares whose difference is five, and x and y are integers? Does this have a root? Does this have a solution? Does this have an integer solution? Suppose I'm given a polynomial, what's called a Diophantine polynomial, which means the coefficients are all integers. The coefficients are 1 times x minus 1 times y squared equals 5. Suppose I'm given such a polynomial, does it have a solution where x and y are integers? Yes, in this case the answer is yes, it does have a solution. If you take x equals, I don't know, 3 and y equals 2, you see 3 squared minus 2 squared is 5. It does have a solution. For an example, what about an equation like this, x cubed plus y cubed equals z cubed? Does it have a solution? It does. The answer is x equals 0, y equals 0, z equals 0. That, for example, it does have a solution like that. But you can ask more interesting questions of the same form. You're given a polynomial x, y, z, a multivariate polynomial and you want to ask, "Is there an integer?" You're given an equation, I want P to be equal to 0. Is there integer assignments to the variables that makes P equal 0? The answer is, it's called the Diophantine problem. In 1900, around the turn of the century, David Hilbert posed this as one of the questions that's going to keep mathematicians busy over the 20th century. He was right. Around the 1970s, Yuri Matiyasevic, I can't say vic. I really am bad at writing Russian names, with earlier contributions from Martin Davis and Julia Robinson, he found out a proof that this is undecidable, which means that given a general polynomial, there is no algorithm that will work through the polynomial and decide whether there are integer assignments that can make the polynomial zero or no such assignments exist. These are examples of problems that you cannot solve by computers. These are unsolvable problems. We've already made our first distinction. We cut the world of problems into problems that are decidable, which means they can be solved in the first place by computer and undecidable, which means these are problems that cannot be solved by a computer no matter what. Because no currently known physical model of computation is capable of solving these problems. Now, even in decidable, not every problem is of interest to us. We want to know what are decidable problems that can be solved fast and problems that cannot be solved fast. Which means not only am I interested in knowing that there exists an algorithm, I want to know there is a fast algorithm that can solve it for large inputs in no time, within the blink of an eye. I'm really interested in knowing the answer between what can be solved fast and what cannot be solved fast. Are there fundamental limitations in the world, in mathematics, in computing, in physics, that make it difficult for us to solve certain problems rapidly? This is going to be the topic of the very next lecture where we are going to talk about the complexity classes between polynomial and exponential time, which separates the notion of a fast algorithm and a slow algorithm. That's coming up in the very next lecture. See you then. Bye.
