# Is there a shortcut to the world?

At the beginning of 2000, the American Clay Institute of Mathematics selected seven “Millennium Awards”: NP Complete Problem, Hodge Conjecture, Poincaré Conjecture, Riemann Conjecture, Yang-Mills Existence and Quality Gap, Weil-Stoke equation and BSD conjecture. The NP complete problem is the first in this list of mathematical problems, the biggest problem in computer science, and perhaps the most difficult of all math problems. P complete problem is P = NP? The problem was first raised by Stephen Cook in 1971. It is the youngest of the seven Millennium Awards and the best one.
What is P and NP?
In our lives, some math problems can be solved quickly, such as buying things to checkout; but some math problems take a lot of time to solve, such as playing chess. With the development of mathematics and computer science, people have come up with better algorithms for some of the more difficult mathematical problems, so the time required to solve them becomes less. If the problem is divided into two types: quick resolution and slow resolution, adding, subtracting, multiplying and dividing is a problem that can be solved quickly. Chess is a slow problem. Of course, there are still many problems. We don’t know where to divide them. one type. So we used a more precise definition of P and NP to classify these mathematical problems.
The P problem contains all the problems that can be quickly solved by computer programs, such as addition, subtraction, multiplication and division. The NP problem means that if you give an answer to a set of questions, you can at least check if the answer is correct at a reasonable time. For example, given a number of 41073317, it is somewhat difficult to do a prime factorization for this larger number. But if you give a possible answer such as 8699 and 4783, you can quickly compare the two numbers to the original large number, and quickly get the 8699 and 4783 numbers are the correct answer. There are many problems in the world, and it is difficult for us to find the answer, but if the answer is given, it is relatively simple to verify that the answer is correct. For example, to make a Sudoku answer, you can easily verify the correctness of the results, but we have not found a best way to solve all Sudoku problems perfectly (imagine 1000×1000 Sudoku instead of 9×9) ), doing Sudoku often uses the method of trials (ie, enumeration).
There is no doubt that the NP problem contains a P question, because it is only necessary to compare the answers to the questions in a step-by-step manner for the P problem.
The hardest problems in NP NP external
everyone thinks the problem NP contains problems than P to be more contained, even if some problems have not been found, of course, still have not been able to prove it. Mathematicians have found that many NP problems are actually interoperable. For example, the nature of the Sudoku problem is the same as the protein folding problem. If you can find the optimal algorithm for solving the Sudoku problem, protein folding is the most important biological problem of the 21st century. It will also be solved. Sudoku and protein folding problems belong to a subordinate NPC (NP-Complete) problem in NP. The NPC problem is the hardest part of NP. The complexity of these problems (the time and space needed to solve the problem) is related to the complexity of the whole class. If we can solve a certain NPC problem quickly, then all NP problems can be solved. Quickly unlock.
The NP problem takes a long time to solve, but it is easy to verify the correctness of the results. Beyond NP, there are still some problems. It is even impossible to verify the results of these problems. For example, it is difficult to judge whether a certain step in chess is the best. There is also a Co-NP problem. Unlike the NP problem, the Co-NP problem can easily output the wrong solution in a reasonable amount of time, rather than verifying the correct solution. Whether the Co-NP problem and the NP problem are interoperable, we do not know. In addition to this, there are a lot of problem categories, and each category takes a lot of time to explain.
P=NP?
NP is important because it contains some very important questions, such as: traveling salesman problem (giving the distance between a series of cities and each pair of cities, solving the shortest circuit that visits each city once and returns to the starting city) ), circuit design problems and database problems, etc. If these problems are solved, our lives will have earth-shaking changes. Therefore, mathematicians have been actively solving various mathematical problems. In the course of this effort, we are sometimes fortunate to find that some NP problems are actually P problems, we have found a shortcut to solve this problem, and there are still many NP problems can not be classified as P. Scientists began to think: Will all the problems in NP eventually become P problems? Still some NP problems are more difficult to solve than the P problem? This is the famous P=NP? problem.
There are two ways to solve the P=NP conjecture. One is to find the solution algorithm for the NP problem, then all the NP problems can be solved. The other is to prove that the algorithm does not exist from the mathematical theory. But many mathematicians now have misunderstandings on this problem. They often assume a possible solution algorithm and then try to prove the error or non-existence of this algorithm. In fact, it proves that the P=NP problem itself is one of the NP problems, which makes us feel more confused.
If P = NP, then we can find a simple way to solve the problem, in other words, humans have shortcuts when solving complex problems. The computer can become very “smart” at once, and you can quickly find a shortcut in a very chaotic situation. When all the information is known, the computer can make a very accurate prediction of the stock market, weather, and game results in a very short time; the computer can easily find an algorithm to know how the artwork is directly hitting the human heart, so The computer can customize his favorite music and works of art for everyone. At the same time, artificial intelligence can be quickly self-optimized, meaning that the end of humanity may come; the foundation of cryptography can easily be cracked, and each of us has no secret at all.
P=NP? The mathematician has no answer yet.