Vol 3 Chapter 556: : This question really is a show

(Look at this chapter as a domineering article. If you do n’t understand it, it ’s better to be a protagonist. This chapter is a preparation for biological genetic engineering in the future. Everyone knows after reading it. Later updates will not appear. This kind of persuasive chapter must be finished with tears ... o (╥﹏╥) o)

Ye Hua looked at several students with a smile: "P = NP?", The first of the seven major problems in the mathematics of the millennium, no one can prove or falsify it. If anyone of you can solve this problem in the future, Immediately went to the Clay Institute for Mathematics to receive a $ 1 million bounty. This reward is still valid until the Millennium announcement. "
"It is not only the first of the seven major mathematical problems in the world, but at the same time it is the easiest mathematical problem to understand. It is actually a problem of Sudoku. This problem was born in 1971 and was born in the field of theoretical computers. A mathematical problem. "
Teaching is a science of teaching and confusing, and Ye Hua can be said to be an undocumented teacher, but this does not prevent him from becoming a qualified lecturer.
"Classmates, in your life, how do you measure a problem? Is it simple or complicated? Or is it easy or difficult?" Ye Hua paced in the classroom, sometimes with a glance at the students to see if they were Listen carefully, no little action can escape the principal's eyes. During the class, these students were quite good, including Liu Lingshuang, who usually loves to do things.
After a while, I asked myself: "It seems that there is no specific standard for quantification, and the question will vary from person to person. But computers are not the same. The computing efficiency of computers is a fixed value and there is no intelligence quotient."
"For example, two problems, a computer from 1 to 10, and from 1 to 1000. Obviously the latter problem takes 100 times longer than the previous problem."
"For a computer, measuring the simplicity or difficulty of a problem depends on how long or how long it takes to solve the problem, because in a certain situation, time and steps are equivalent. A definition is called time complexity. , The smaller the time complexity and the fewer the problems, the simpler it is. But what else do we have to consider? "
After talking about Ye Hua, they looked at a few of them, and after a while, Liu Ling said, "You have to consider the space occupied by the computer."
"The answer is completely correct."
The hacker girl was praised secretly, and the computer is a good thing for this heroine.
Ye Hua cast a praised look on her, which was regarded as a reward, and then said, "Let ’s put space aside, let's talk about time today, for example ..."
There is nothing easier to understand than the classic "lift a chestnut".
"One question, now I will give you n numbers and ask to choose the largest one. How many steps will it take? Who knows?"
As soon as the voice fell, the youngest Ning Jie responded quickly: "n-1 steps."
"correct answer!"
Ye Hua nodded, and the mathematical genius Ning Jie answered so quickly that he expected it to bring up a floating screen to list a series of numbers: "The method is actually very simple, first compare the first two, and take the largest one and The third number is compared, then the largest number is compared with the fourth number, and so on, and n numbers are compared n-1 times. "
"The second question still gives n numbers, but this question requires n numbers to be sorted in order. How many steps does it take?"
Ning Jie said again without hesitation: "Need n (n-1) / 2 steps."
Ye Hua nodded again: "The answer is correct. Can you introduce the calculation process with other students, Ning Jie?"
Ning Jie replied immediately: "The first method to select the largest number requires n-1 steps, and then select the largest number of all remaining numbers to use n-2 steps, and so on is (n-1) + (n-2) + (n-3) + ... until the answer is n (n-1) / 2. "
Liu Lingshuang saw it quickly and immediately understood that this is not the "bubbling method" in computer programming. The hacker girl naturally understands at a glance. In fact, these are simple problems. The eight students present can quickly understand .
Ye Hua went on to say: "Obviously, as n increases, the difficulty of the ranking problem is higher than the previous selection of the largest number. N-1 When this n is large, -1 can be omitted, is there any? The magnitude of the impact is determined by n, and the magnitude of the second problem time is determined by n ^ 2, and others can be omitted, including coefficients. "
At this point, Ye Hua called up a floating large screen that simulates a blackboard, replaced the chalk with his fingers, clicked white on the swatch, and then listed the formula on the panel: "Use the progressive symbol O, the first question The amount of calculation is expressed as O (n), and the second problem is expressed as O (n ^ 2). Comparing the two problems, it is found that O (n ^ 2) is more difficult as n increases, which is easy to understand because n ^ 2 is greater than n. "
Ye Hua continued to write and said, "n, n ^ 2, n ^ 3, etc. or their combination is called a polynomial. This type of problem is the P type problem in the" P = NP? Problem ". Is there a harder problem? Of course there are, for example, prime numbers. "
As Ye Hua looked back at the students, "Is a natural number a prime? How many steps does it take to solve it? The stupid method is to divide one by one, starting from 1 and dividing it into √a, so we use √a at most. A complete description That is: is a n-digit natural number a prime? "
Ye Hua, who fully took the role of lecturer, immediately turned around and continued to list on the floating screen: "The decimal number with n digits can be expressed as: 10 ^ n-10 ^ (n-1), then the problem with prime numbers is obviously: O (√ 10 ^ 2), even binary numbers: O (√2 ^ n), students see, does the prime number problem increase exponentially as the number of digits n increases? This is a terrible upward trend. "
"All the questions mentioned above have one thing in common. No matter whether it is difficult or not, it will be much easier to give an answer to verify it. For example, a certain a is not a prime number because it can be divided by the number b. It works, it can be verified in polynomial time. Then all such problems are NP-type problems. "
Ye Hua looked around the eight students and saw that they had no doubts in their eyes, and apparently understood them, and were very satisfied with their performance.
"N stands for non-deterministic. The standard definitions of P and NP are related to Turing machines. P can solve problems in polynomial time, and NP can be verified in polynomial time no matter how difficult it is. This is the difference between the two. Pay attention to . Does that mean that NP problems are more difficult than P-type problems? The answer is no, because P-type problems are NP-type problems, and we must also pay attention to this. "
Ye Hua paced in front of the students again and methodically preached: "In mathematics or in the computer field, the difficulty of a problem depends largely on the calculation method. The computer is the algorithm, and the algorithm is the computer. Soul. It ’s the same even for math problems. Some methods of the same problem are simple and fast. It may be a problem of missing an auxiliary line. "
"All the methods mentioned above are dead methods, just to achieve the purpose. The term in the computer is called" bubble method ", and its complexity is O (n ^ 2). The development of superior algorithms can reduce the complexity, such as the quick sort method. The complexity is O (nlogn), which is obviously smaller than n ^ 2, so the difficulty of a problem in the computer field depends on whether its algorithm is superior or not. "
"It is not difficult to understand. People study the algorithms of every computer in order to reduce NP-type problems to P-type problems. But there are so many problems to find the year of the monkey? So, since NP problems have one thing in common, that is, , They can all be verified in polynomial time, do they have another thing in common? "
Ye Hua asked himself:
"So we assume there is a 'universal algorithm' that can reduce all NP problems to P-type problems. This is the" P = NP? "Problem. You don't even have to figure out what this 'universal algorithm' is, as long as you can prove or falsify, you can win a million prize. "
Immediately looked at the students: "At the same time, we will find that there are such a small class of problems in the NP problem, they are obviously much harder than the P-type problems, and it feels that these problems are the least likely to be P-type problems. Moreover, these problems also have one thing in common. Once it is proved that any one of them has a superior algorithm that can be reduced to a P-type problem, the other problems can also be reduced to a P-type problem. In other words, as long as it is proved that one of them belongs to P, That is P = NP. Then this small class of problems is referred to as NP-C, which is the NP complete problem. "
When Ye Hua explained here, everyone can understand well, but the next question is not so friendly to them.
"NPC is obviously more difficult than P-type problems. For example, it is close to our life. For example, a Meituan takeaway brother lives at point A. He wants to go to n places to deliver takeaways. They are all known. Then how can this takeaway brother walk through every place and finally return home to ensure that the distance he travels is the shortest? "
At this point, Ye Hua paused, took a glass of water and sipped a moist throat, and eight students frowned, among which Ning Jie, who was the most gifted in mathematics, was also suspicious.
After a period of time, no one took the initiative to answer it. Ye Hua said, "The problem is, how many possibilities are there for the take-away brother? How to describe it mathematically?"
The students all looked at Ye Hua, who said, "Then the obvious result is the factorial O (n!) Of n. So you can see that this complexity can be much larger than the problem described earlier. Because O (n!) ≈√2π (n / e) ^ n, this number is much larger than the exponent with a constant base. "
Ye Hua turned around and swiped on the blackboard simulated by the floating screen: "The factorial of the column is 19, it seems that this number is not large, but the formula of the column: 19! ≈ 1.21 × 10 ^ 17, even if this number is too large It is the most classic computer now. It is assumed that he can row one million times per second and it will take about three thousand years. Therefore, the takeaway brother delivers so many goods every day. In theory, he just wants to find the best route. Impossible. "
"But students note that the difficulty and simplicity here represent a trend. When n is small, the calculation amount of the human brain can be quickly calculated. For example, Sudoku, a 3 × 3 Sudoku elementary school student will Well, classmates, let me give you a 100 × 100 try? For example, a 100 × 100 square grid, give a number of 1 ~ 100 as a clue, and then ask to fill the rest of each and ensure that both 1 to 100, this problem can't be solved quickly even with the best computer in the world today. "
"So obviously ~ EbookFREE.me ~ This problem is also an NPC problem. Have you ever played minesweeping, Tetris and other small games? They are also NPC problems." Speaking of which, this knowledge point is also explained, Ye Hua finally said:
"So if you can prove that P = NP, then it will be a great contribution to all humans. For example, the complexity of protein folding in the human body is the NPC problem. Once it is proved that it is a P ... laugh?"
Seeing Liu Ling's double-chuckled smile, Ye Hua stared at her pretentiously. This little Nizi, he could be seen, among the eight students, she was the skinniest.
Slightly coughed, and then said the previous topic: "... so as long as it is proved to be a P-type problem, many diseases can be solved, and cancer and AIDS are not a problem. But I want to prove that P = NP is quite It ’s not easy, because
Prove P = NP
first is a question, right? So here comes the problem, it is an NPC problem in itself ... "
It seems that I have felt deeply malicious and full of hostility caused by this problem. This problem is indeed a show. It is indeed the first of the seven major mathematical problems in the world that have left mathematicians all over the world helpless.
... ()