Okay. Let's put aside this non-computable functions and leave it to philosophers. We're now going to concentrate only on computable functions. It appears that these computable functions are not all the same. Some of them are easier to compute and some are harder to compute, and the reasons of these differences are not exactly clear. Honestly, it is not clear at all. Imagine two very similar problems. Each of them takes some graph as its input. So, you have some vertices, some edges, and a graph. The question for the first problem is if there is an Euler's path in this graph? The question for the second problem is if there is a Hamilton path in this graph? The Euler's path is the path which visits every edge exactly once and the Hamilton path is the path which visits each vertex exactly once. The first problem is known to be easy. We have an effective algorithm for solving it. The second problem is believed to be hard. We don't know an effective algorithm for solving it and there are reasons to believe that this effective algorithm doesn't even exist. Now, I, again, use some unclear theorem and effective for a good algorithm, assuming that if there are effective or good algorithms, there also exist ineffective or bad algorithms. Here, I allude to some hidden parameter which allows me to estimate algorithms, and to say that some of them are good, some of them are bad, and some are worse. There are actually plenty of such possible parameters, and here I use time or number of steps of deterministic turing machine needed to perform the computation. So, here for these two problems which are quite similar, we have very different results for one problem. We have an algorithm which requires not much time. For the second problem, we don't. Let's consider another example. For example, we have two integers, two, maybe, natural numbers, a which has n digits, and b which also has n digits. Now, we're going to add these numbers, a and b, using the column addition method we learned at school. This method will require at most two n of elementary additions, and elementary addition is just the addition of one digit to another digit. So, we see that the complexity, the number of steps we need to perform to accomplish the result, depends on this n, the number of digits. We can say that the complexity of the problem is O of n. So, it's linear regarding the number of digits in the numbers we have to add. Now, imagine that we have to multiply these numbers. So, instead of summing them, we have to multiply them. This will require approximately n square of elementary or table multiplications which means that the complexity of the multiplication problem is O of n squared. We can see now that if when n grows, the complexity of multiplication grows faster than the complexity of addition. Anyway, we don't consider multiplication problem to be very hot. Actually, any infinite power here tells us that the problem is not so bad. All the problems for which we have a polynomial complexity algorithm, we consider them to be tractable. All such problems form the infinite class called b. So, all these problems for which we know or for which can exist an algorithm with polynomial complexity defined like this. A set of this class of tractable problems which we call P. There is another interesting class of problems which is called NP. Here, P stands for polynomial, and NP for non-deterministic polynomial. The problems from the class in P are those problems or those functions for which we can easily or polynomially check and answer. The ability to check the answer is important. Imagine one day, one of your friends come to you and says that he or she developed a computer program, a chess player computer program which cannot lose. Now, can you easily check this statement? I believe that, no, you cannot because, actually, you will have to play all possible chess games with this program to understand if it can loose or it cannot. Now, imagine another situation that this friend came to you and tells you that he or she found a Hamilton path on some graph. Now, can you check this statement? Yes, you can. You can just follow this path provided to you by this friend and see if it visits every edge exactly once. So, the complexity of this check will be O of n where n is the number of vertices in this graph. So, this statement is easily checkable, and the finding of Hamilton path in some graph is, thus, an NP problem, because maybe it's hard to find this path, but if somebody finds it, it is easy to check if it is correct. Out of those that P belongs to NP, because, for any problem from P, we can easily check the answer just by solving this problem with polynomial algorithm. But the stronger assertion, if P is less than NP, is one of the most famous, most important unproven theorems in modern complexity theory. Because this theorem is not proven, we still have to consider these two options on the slide here, if P is not equal to NP, here, and if P equals to NP. So, you see class P here, class NP. Nowadays, it is believed that there are problems which belong to NP but do not belong to P, though we cannot prove it. One of such important problem is factoring problem. Imagine that you have found two different big prime numbers, p and q, each like 10,000 digits. You multiply them, and you get the product. Both these tasks are like finding big primes and multiplicating them is feasible for modern computers. Then, you give me this number n, and you ask me if I can find these original factors. We both know that there is only one set of such factors. So, theoretically, I can do this, but, in practice, I cannot because for all algorithms to solve this task, we know by now, they all will require too many steps, and with the reasonable assumptions about the growth of our computing power, I will not finish the execution of these algorithms until my death, or even until the Solar System's death. As I said, they require too many steps. So, this problem of factor is theoretically solvable. It is computable. But it is intractable because, in practice, we can not solve this problem. To finish here on a brighter note, in 1994, an American mathematician, Peter Shor, designed a quantum algorithm which solves this factoring problem in polynomial time. So, now quantum computers can solve problems that are intractable for classical computers. All of them? Well, probably not. Here on these diagrams, you see another interesting class which is called NP-Hard. These are the problems for which any problem from NP are polynomially reducible which means that, if you have some magic black box which solve some problems from here effectively, with this magic box, we can polynomially solve any problem from here, from the class NP. In 1972, an American-Canadian mathematician, Stephen Cook, proved that the intersection of this class of NP hard problems with the class NP is not empty. Now, this intersection is called NP-complete or the class of NP-Complete problems or NPC, which are the most difficult problems in the class NP. So, if you find an effective solution for some problem from here, we can effectively solve any problem from the class NP with this solution. Unfortunately for factoring problem, it is not yet proved that it belongs to NP-Complete problems, and, actually, it is believed that it does not. So, it's somewhere here. But for all these problems, for NP-Complete problems, in general, we have a better general solution for quantum computers than we have for classical ones. For these problems from here, we still cannot say anything reassuring yet which means that maybe you will be the first mathematician who will find, who will develop some quantum algorithm which effectively solves some problems from here, some NP-Hard problems.