NP problem is really hard to understand.

Original address:/csshuke/article/details/74909562

I hope that through this article, not only computer-related professionals can understand and distinguish what is a P-type problem and what is a NP-type problem, but also non-professionals such as friends who study liberal arts can understand it to a certain extent.

There is a joke in the field of programmers, that is, when a buddy went to google for an interview, he was asked a question: When P=NP, and then his answer was "When N= 1". This is the first time I've heard about the P=NP problem, probably when I'm about to graduate and look for a job.

These days, the headlines of science and technology news have been blown up by Alpha Dog vs. Li Shishi. Although I am not an AI expert, I also want to write something to talk about this interesting thing from the perspective of ordinary people. When collecting information, I saw NP problem again, so I wanted to take a break and write an article "How to play AI?"? Before, let's talk about this NP problem.

The simplest definition is:

P question:

A problem can be solved within the time complexity of polynomial ().

NP problem:

The solution of a problem can be verified in polynomial time.

NP-hard problem:

Any np problem can be reduced to this problem in polynomial time, but the problem itself is not necessarily NP problem. Reduction means that in order to solve problem A, problem A is reduced to another problem B, and solving problem B also indirectly solves problem A. ..

NPC questions:

It is both NP-hard and NP-hard.

Although this definition is simple, for people who are exposed to P and NP for the first time, it is like asking you what is "gravitational wave" a while ago, and you answer: gravitational waves are ripples in time and space. I hardly got any meaningful understanding from the answer. So I hope that not only computer-related professionals can understand the content, but also liberal arts students can understand it to a certain extent.

At present, although computers have become very popular, some people use them to surf the Internet, play games and watch movies, but few people still care. The essence of computers is computers, which bring entertainment and convenience to people's daily lives while demonstrating their great computing power. All kinds of software used in our daily life are actually a set of computer programs, which can be regarded as a series of algorithms, and the role of computer hardware we see is to deal with these algorithms. The algorithm mentioned here is not only simple addition, subtraction, multiplication and division, but also includes the following elements:

Arithmetic operations: addition, subtraction, multiplication, division, etc.

Logical operations: OR, AND, NOT, etc.

Relational operations: operations such as greater than, less than, equal to and unequal to.

Data transmission: input, output, assignment and other operations.

And the order of processing these operations is controlled by the control structure. Speaking of which, I'm a little worried that some friends don't quite understand. For example.

How do we pick out the biggest number from n numbers? Let's keep it simple. We just need to compare them one by one. Specifically, compare n with n- 1 and write down the larger number. Then we compare this number with n-2, and write down the larger number for comparison with the last number. This whole comparison process can be called an algorithm, and this algorithm contains the above elements. The number n given to us is the input data of the algorithm, and the maximum number we want to select is the output data of the algorithm. Among them, some basic arithmetic operations or relational operations must be used when judging the size.

I hope you can basically understand what an algorithm is, because I will spend a little time talking about the time complexity of the algorithm. To calculate or solve a problem, the problem usually has a size scale, which is represented by n. We refer to the above example and find the largest number from the n numbers. This n is the size of the problem. How to find it? We have to compare n- 1 times to get the result. This n- 1 time can be understood as the time spent, that is, the time complexity. For another example, the number of n is sorted from the largest to the smallest, and n is its scale. If we follow this method: get the maximum from the number of n for the first time, get the maximum from the number of n- 1 for the second time, and so on, the number of comparisons required is n(n- 1)/2. The method we use is called algorithm, so n(n- 1)/2 is the time complexity of the algorithm. For time complexity, when n is large enough, we only pay attention to the highest power term, and other terms can be ignored. In addition, its constant coefficient is not important, and we only pay attention to the square of n(n- 1)/2, which is a professional expression of the time complexity of this problem.

In fact, time complexity does not mean how long it takes a program to solve a problem, but how quickly the length of time required by the program increases when the scale of the problem expands. That is to say, for a high-speed data processing computer, the efficiency of processing a specific data cannot measure the quality of a program, but should depend on whether the running time of the program is the same after the scale of this data becomes hundreds of times, or whether it is hundreds or tens of thousands of times slower. No matter how big the data is, the processing time of the program is always so much, so we say that the program is very good and has time complexity, which is also called constant complexity; The time complexity of this program is, for example, to find the maximum number of n; Such as bubble sorting, insertion sorting, etc. , the data expansion is 2 times, and the time is 4 times slower, which is complexity. There are also some exhaustive algorithms, the time required increases geometrically, which is exponential complexity or even factorial complexity. There will be no complexity, because the previous "2" is a coefficient, which will not affect the time growth of the whole program at all. Similarly, the complexity of is also complexity. So we will say that a new program is less efficient than the latter. Although the former is better than the latter when n is small, the latter will be far more complex with the slow growth of data scale. We also said that the complexity is less than the complexity of.

All right, time to get to the point. It is easy to see that the previous types of time complexity can be divided into two levels: one is,,, and so on. We call it polynomial-level complexity because its scale n appears in the base; The other is the sum complexity of non-polynomial level, and its complexity is often unbearable for computers.

It's time to introduce the concepts of P problem and NP problem: if a problem can find an algorithm to solve it within the time complexity of polynomial, then it belongs to P problem. The understanding of NP problem is not NotP, and NP problem is not a non-P problem. NP problem refers to a problem whose solution can be verified in polynomial time. Another definition of NP problem is that a solution can be guessed in polynomial time. I don't think it is necessary to give too many examples to illustrate the P-type problem. The problems mentioned above, such as finding the maximum number and sorting, are all P-type problems, and another example is needed to better understand NP problems.

Factorization of large integers-For example, someone told you that the number 9938550 can be decomposed into the product of two numbers. You don't know if it is right, but if you are told that these two numbers are 1 123 and 8850, it can be easily verified with the simplest calculator.

Shortest path problem-the shortest path, that is, the path from one vertex to another along the edge of the graph, the sum of the weights of each edge is the smallest.

As shown above, for example, if I tell you that the shortest path from 0 to 5 is 22, I only need 0- > to verify. 1, plus1->; 5, 13+9 = 22, and the time complexity remains unchanged. If it is expanded from 6 points to n points in the above figure, the algorithm time required for the verification process is also very heterogeneous. If we don't tell you how important the shortest path is and need to be solved by an algorithm, we can "guess" its solution like this: first, find a scheme with a total distance of no more than 100, assuming that we can "guess" a very lucky route so that the total length does not exceed 100, then we only need to guess one route n times at a time. Next, we need to find a scheme with a total length less than 50. If we can't find it, we will raise the threshold to 75 ... Suppose we finally find a scheme with a total length of 90, but we can't find a scheme with a total length of less than 90. We finally "guessed" that the solution of this traveling salesman problem is a route with polynomial time length of 90.

Is there a problem that is not NP-hard? Yes It is for these problems that the verification solution cannot be completed within polynomial time complexity. For example, ask: Is there no Hamilton cycle in a graph?

Starting from any point in the graph and finally returning to the starting point, it becomes a Hamiltonian loop if and only if it passes through every node in the graph once.

To verify Hamilton loop, we only need to walk once on a given path to see if each node only passes once, but to verify that there is no Hamilton loop, we need to walk once on each path, otherwise we dare not say that there is no Hamilton loop.

The reason why NP problem should be defined specifically is that we will not try to find its solution with polynomial time complexity for those problems that cannot be verified with polynomial time complexity, which is a bit awkward, but we should understand it after reading it several times. Generally speaking, it takes a long time to tell you the answer to a question and let you verify it. This can be likened to using an algorithm to solve it, and it will definitely take longer.

Then, on the other hand, all P problems are NP problems. That is to say, if you can solve a problem polynomial, you can certainly verify the solution of a problem polynomial-since all the positive solutions have come out, you only need to compare any given solution and calculate it for you again with polynomial time complexity. The key point is that people want to know whether all NP problems are P-type problems, that is, whether all problems that can be verified in polynomial time can also be solved in polynomial time. We can explain it from the perspective of set. If all P-class problems belong to one set P and all NP-class problems belong to another set NP, then obviously there are P's belonging to NP. Now all the research on NP is focused on one question, that is, is there P=NP? The so-called "NP problem" is actually a sentence: prove or overthrow P=NP.

At this point, what is a P-type problem and what is a NP-type problem is over. There may be some people who are not very clear about it, so let's summarize it in popular but not very strict terms.

P-type questions refer to those whose answers are easy to be worked out by computers.

NP-class questions refer to those questions whose answers are known and can be easily verified by computers.

The next topic is why P=NP is difficult to prove. Just watch it boring. At least you can distinguish p from NP. The next content will be even more brain-burning.

Let's look at a set graph first, which reflects P=NP or p! =NP, in which two new concepts NP-Hard and NPC appear. To explain why there is no conclusion that P is equal to NP, we must first understand NPC and NP-Hard.

Before introducing NPC, let's learn a concept-reduction. Simply put, a problem A can be reduced to a problem B, which means that the problem A can be solved by the solution of the problem B, or that the problem A can "become" the problem B. For example, there are two problems: solving a linear equation with one variable and solving a quadratic equation with one variable. Then we say that the former can be simplified to the latter, because we know how to solve the quadratic equation of one variable, so we can definitely solve the quadratic equation of one variable, because the quadratic equation is a quadratic equation with zero quadratic coefficient. "Problem A can be simplified to problem B", so it is easy to understand that problem B is more difficult than problem A, and the time complexity of solving problem B should be greater than or equal to that of solving problem A, and simplification also has an important property: transitivity. If problem A can be attributed to problem B and problem B to problem C, then problem A must be attributed to problem C, which should be well understood. Now let's talk about the standard concept of reduction: if we can find such a changing law that the input of any program A can be transformed into the input of program B according to this law, so that the outputs of both programs are the same, then we can say that problem A can be reduced to problem B.

From the definition of reduction, we can see that the reduction of one problem to another increases the time complexity and the application scope of the problem. Through the continuous reduction of some problems, we can constantly look for algorithms with higher complexity but wider application scope to replace those with lower complexity but only for small-class problems. So if a NP problem is constantly reduced, is it possible to find a super NP problem with the highest time complexity? The answer is actually yes. In other words, there is such a NP problem, and all NP problems can be attributed to it, and it is not only a problem, but also many problems, and it is a kind of problem. This kind of problem is the legendary NPC problem, which is NP complete. So the definition of NPC problem is simple. A problem that satisfies the following two conditions is the NPC problem. First of all, it must be NP problem; Then, all NP problems can be summed up in it.

Because all NP problems can be attributed to NPC problems, as long as any NPC problem finds a polynomial algorithm, all NP problems can be solved by this algorithm, so NP is equal to P, so there is no effective polynomial algorithm for NPC problems at present, and it can only be solved by exponential or even factorial complexity algorithm, that is to say, if we can find an NPC problem that can be solved by polynomial time complexity, it is proved that P=NP.

And when it comes to NP-hard problems. NP-Hard problem is a kind of problem that satisfies the second definition of NPC problem but does not necessarily satisfy the first definition, that is, all NP problems can be attributed to it, but not necessarily NP problems, that is, even if a polynomial algorithm of NPC problem is found one day, NP-Hard problem cannot be solved by polynomial algorithm, because it is not NP problem and it is difficult to verify the answer.

The following is an example of a logic circuit in Matrix67 article to illustrate the NPC problem.

Logic circuit problem refers to such a problem: given a logic circuit, ask whether there is an input that makes the output true.

What is a logic circuit? A logic circuit consists of several inputs, one output, several "logic gates" and many wires. Look at the following example, you will understand it immediately without explanation.

This is a relatively simple logic circuit. When input 1, input 2 and input 3 are true, true, false or false, true and false respectively, the output is true.

Is there a logic circuit whose output can't be true anyway? Yes Here is a simple example.

No matter what the input is, the output of this logic circuit is false. Suppose this logic circuit does not have a set of inputs that make the output true.

Back to the above, given a logic circuit, ask whether there is an input that makes the output true. This is the logic circuit problem.

The logic circuit problem belongs to NPC problem. This is strictly proved. It obviously belongs to NP problem, which can directly prove that all NP problems can be attributed to it. The proof process is quite complicated, which roughly means that the input and output of any NP problem can be transformed into the input and output of a logic circuit (considering that there are only some operations of 0 and 1 in the computer), so for an NP problem, the problem is transformed into finding an input that satisfies the true result (that is, a feasible solution).

At present, there is no algorithm for solving NPC problems with polynomial complexity, so once such problems become polynomial complexity solvable, many problems can be solved by existing computer technology. Just like a computer playing Go, it is obviously very simple to verify the result of a chess game, but to ensure that every game can be won, the current method requires the computer to enumerate all the possibilities and search for the final winning chess path according to the change of each move, which is obviously beyond the current computer performance. Because the state space complexity of Go reaches 10/72 square, and the game tree complexity of Go reaches 300 power of 10, it may not be intuitive to just look at numbers. In short, Go has changed more than the number of atoms in the universe!

Therefore, for a game like Go, if artificial intelligence wants to defeat human beings, it needs to meet either of the following two conditions:

The computer is infinitely powerful and can exhaust all possibilities;

A new algorithm is proposed, which can guarantee to win without exhaustive.

At present, what Google's AlphaGo does is to improve the efficiency of exhaustive search by optimizing the algorithm, and at the same time use the existing big data and cloud computing to improve the computing performance. The next article will introduce how the AI game is played in more detail, so stay tuned.