Seven mathematical problems in the world:
1, P/NP problem (p versus NP)
2. Hodge conjecture.
3. The Poincare conjecture that has been confirmed.
4. Riemann conjecture.
5. Young-Mills existence and mass gap.
6. Existence and smoothness of Naville-Stokes.
7. Burch and swinton Dale conjecture.
The so-called seven mathematical problems in the world are actually the seven mathematical problems announced by the Clay Institute of Mathematics in the United States on May 24, 2000. Also known as the Millennium Prize puzzle. According to the rules formulated by Clay Institute of Mathematics, the solutions to all difficult problems must be published in mathematical journals and verified by all parties. As long as they pass the two-year verification period, each solver who solves a problem will get a bonus of $654.38+$00,000. These problems echo the 23 historical mathematics problems put forward by German mathematician david hilbert in 1900. One hundred years later, many puzzles have been solved. The solution of the Millennium Prize puzzle is likely to bring breakthroughs in cryptography, aerospace, communication and other fields.
One: P/NP problem
P/NP problem is one of the most difficult mathematical problems in the world. In the field of computational complexity theory of theoretical informatics, it has not been solved so far, and it is also one of the seven Millennium prize problems of Clay Institute of Mathematics. P/NP problem contains the relationship between complex classes P and NP. 197 1 year, Steven Guck and Leonid Levin raised the following question relatively independently, that is, are the two complexity classes P and NP the same (P=NP? )。 Complexity class P is all the problems that a deterministic Turing machine can solve in polynomial time. NP-like consists of all decisive problems that can verify whether the solution is correct in polynomial time, or equivalently, a set of problems whose solutions can be found in polynomial time on uncertain Turing machines. Probably, the biggest unsolved problem in computing theory is about the relationship between these two types: are P and NP equal? In the survey of 100 researchers in 2002, 6 1 people thought that the answer was negative, 9 thought that the answer was positive, 22 were uncertain, and 8 thought that the question might be independent of the accepted axiom, so it could not be proved or falsified. The correct answer will be rewarded with 1 10,000 USD. NP complete problem set (or NPC) plays an important role in this discussion. They can be roughly described as those in NP that are least like those in P (see NP- complete theory for exact definition details). Computer scientists now think that the relationship between P, n P and NPC classes is as shown in the figure, in which P and NPC classes do not intersect.
Suppose the complexity level graph of P ≠ NP. If P = NP, the three categories are the same. Simply put, P = NP Question Q: If the positive answer to the yes/no question can be quickly verified, can the answer be quickly calculated? Here is an example to give you some feelings about this problem. Given a large number y, we can ask whether y is a composite number. For example, we may ask 533082906 1 1 whether there are extraordinary factors. The answer is yes, although it is more troublesome to find the factors by hand. On the other hand, if someone claims that the answer is "Yes, because 224737 is divisible by 533082906 1 1", we can quickly verify it by a division. It is much easier to verify that a number is a divisor than to find an obvious divisor. The information needed to verify a positive answer is also called evidence. So our conclusion is that given the correct proof, the positive answer to the question can be verified quickly (that is, in polynomial time), which is why the question belongs to NP. Although this special problem has recently been proved in class P (see the following reference on "prime numbers in P"), it is not obvious at all, and many similar problems are considered not to belong to class P. As mentioned above, limiting the problem to the "yes/no" problem has not changed the original problem (that is, it has not reduced the difficulty); Even if we allow more complicated answers, the final question (whether FP = FNP) is equivalent.
The result of proving difficulty
Although millions of dollars in bonuses and a lot of research without substantive results are enough to illustrate the difficulty of the problem, there are some formal results that can prove why the problem may be difficult to solve. One of the most frequently cited results is the design Oracle. Imagine that you have a magical machine that can solve a single problem, such as determining whether a given number is prime or not. You can solve this problem instantly. Our new question is, if we are allowed to use this machine at will, is there any problem that we can verify in polynomial time but can't solve in polynomial time? Results According to the problems that the machine can solve, both P = NP and P ≠ NP can be proved. The consequence of this conclusion is that any result that can prove the existence of the machine by modifying the Oracle will not solve the problem. Unfortunately, almost all classical methods and most known methods can be modified in this way (we call it relativism). If this is not too bad, a result proved by Razborov and Rudich in 1993 shows that, given a concrete and credible hypothesis, in a sense, the proof of "nature" cannot solve the P = NP problem. This shows that some methods that seem most promising now are unlikely to succeed. As more and more such theorems are proved, there are more and more pitfalls to be avoided in the possible proof methods of this theorem. This is actually the reason why NP- complete problem is useful: if there is a polynomial time algorithm for NP- complete problem, or there is no such algorithm, it will be possible to solve P = NP problem in a way that is not excluded by the above results.