(Everyone should read this chapter as a student of Bawen. If you don’t understand, just pretend to be the protagonist. This chapter is to pave the way for future biogenetic engineering. You will know it after reading it, and subsequent updates will not appear.
This kind of chapter about persuading people to quit, I will definitely finish it with tears in my eyes...oo)
Ye Hua looked at several students and smiled: "As the first of the seven major problems of mathematics in the millennium, p=np? No one can prove or falsify the problem until now. If any of you can solve this problem in the future, you can go there immediately.
The Clay Institute of Mathematics in the United States received a bounty of US$1 million, and this bounty was still valid until the millennium when it was announced."
"It is not only the first of the seven major mathematical problems in the world, but it is also the easiest to understand among the seven problems. It is actually a Sudoku problem. This problem was born in 1971 and was born in the field of theoretical computers.
A math problem."
Teaching is a science that involves imparting knowledge and solving doubts, and Ye Hua can be said to be an unlicensed teacher, but this does not prevent him from becoming a qualified lecturer.
"Students, how do you measure a problem in life? Is it simple or complex? Or easy or difficult?" Ye Hua paced in the classroom, sometimes using his peripheral vision to check whether several students were there.
Listen carefully, and no small tricks will escape Principal Ye's notice. These students are quite well-behaved during class, including Liu Lingshuang, who usually likes to make trouble.
After a moment, he asked and answered himself: "There seems to be no specific quantitative standard for this, and the question will vary from person to person. But computers are different. The calculation efficiency of a computer is a fixed value, and there is no intelligence quotient."
"For example, there are two problems: a computer displays from 1 to 10, and from 1 to 1000. Obviously, the latter problem will take 100 times longer, which is more difficult than the previous problem."
"For a computer, the simplicity or difficulty of a problem is measured by the time or number of steps it takes to solve the problem. Because under certain circumstances, efficiency and the number of steps are equivalent. To give a definition, it is called time complexity.
, the smaller the time complexity and the fewer problems, the simpler. But what should we consider in the actual situation?"
After speaking, Ye Hua looked at them. After a while, Liu Lingshuang said: "We have to consider the space occupied by the computer."
"The answer is absolutely correct."
The hacker girl was secretly happy to be praised. Computers are this heroine's specialty.
Ye Hua cast a look of praise at her, which was regarded as a reward, and then said: "Put aside the issue of space. Let's talk about the issue of time today. For example..."
Nothing is easier to understand than the classic "give me a chestnut."
"As a question, I will give you n numbers and ask you to select the largest number among them. How many steps will it take? Who knows?"
As soon as he finished speaking, the youngest Ning Jie quickly responded: "n-1 steps."
"Correct answer!"
Ye Hua nodded. The little math genius Ning Jie answered so quickly because he expected it. He called up the floating screen and listed a series of numbers: "The method is actually very simple. First compare the first two and take the largest number and
Compare the third number, then take the largest number and compare it with the fourth number, and so on, take n numbers and compare n-1 times."
"The second question still gives n numbers, but this question requires sorting the n numbers from large to small. How many steps are needed?"
Ning Jie said again without thinking: "It takes n(n-1)/2 steps."
Ye Hua nodded again: "The answer is correct. Ning Jie, can you introduce the calculation process to other students?"
Ning Jie immediately replied: "Using the method just now, it takes n-1 steps to select the largest number first, and then n-2 steps to select the largest number among all the remaining numbers. By analogy, it is (n-1)+
(n-2)+(n-3)+…The answer you add until the end is n(n-1)/2.”
Liu Lingshuang understood quickly at a glance. Isn't this the "bubble method" in computer programming? The hacker girl naturally understood it at a glance. In fact, these were simple questions, and the eight students present could quickly understand them.
.
Ye Hua continued: "Obviously, as n increases, the difficulty of the sorting problem becomes higher than the previous difficulty of selecting the largest number. n-1 When n is very large, -1 can be omitted. Is there any possibility?
The magnitude of the influence is determined by n. The magnitude of the second problem time is determined by n^2. Others can be omitted, including coefficients."
At this point, Ye Hua brought up a large floating screen that simulated a blackboard, used his fingers instead of chalk, clicked white on the color board, and then listed the formulas on the panel: "Use the progressive symbol o to represent the first question.
The amount of calculation is expressed as o(n), and the second problem is expressed as o(n^2). When comparing the two problems, it is found that as n increases, o(n^2) is more difficult, 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 are called polynomials. This type of problem is the p type of problem p=np?. Are there any more difficult problems?
?Of course there are, such as prime number problems."
As he spoke, Ye Hua looked back at the students: "Is a natural number a a prime number? How many steps are needed to solve it? The stupid way is to divide one by one, starting from 1 to √a, so at most √a steps are used. Complete description
That is: Is an n-digit natural number a a prime number?"
Ye Hua, who fully assumed the role of lecturer, immediately turned around and continued to list the formulas on the floating screen: "An n-digit decimal number can be expressed as: 10^n-10^(n-1), so obviously the prime number problem is: o(√
10^2), even binary numbers are: o(√2^n). Students, look, as the number of digits n increases, have the prime number problems increased exponentially? This is a very scary upward trend."
"All the questions mentioned above have one thing in common. No matter whether it is difficult or not, as long as you give an answer to verify, it will be much easier. For example: a certain a is not a prime number because it can be divided by the number b. Then the verification
It just works and can be verified in polynomial time. Then all such problems are np problems."
Ye Hua looked around the eight students and saw that there was no confusion in their eyes. It was obvious that they all understood and was very satisfied with their performance.
"n represents non-determinism. The standard definitions of p and np are related to Turing machines. P can solve problems in polynomial time, while np can be verified in polynomial time regardless of whether it is difficult or not. This is the difference between them. Please 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. This should also be noted."
Ye Hua paced in front of the students again and lectured in an orderly manner: "In mathematics or the computer field, the difficulty of a problem depends largely on the calculation method. Computers are algorithms, and algorithms are computers.
Soul. Even when doing math problems, it’s the same. There are simple and fast methods for the same problem, maybe it’s just a matter of missing an auxiliary line.”
"The methods mentioned above are all dead methods. Just achieve the goal. The term in computers is called 'bubble method', and its complexity is o(n^2). The complexity can be reduced by developing superior algorithms, such as quick sorting.
The complexity is o(nlogn), which is obviously smaller than n^2, so in the computer field, the difficulty of a problem depends on whether its algorithm is superior or not."
"Then it is not difficult to understand that the purpose of people studying every computer algorithm is to reduce np problems to p problems. But there are so many problems, how can we find the monkey year, horse month? Well, since np problems have one thing in common, that is,
, they can all be verified in polynomial time, is there another thing they have in common?”
Ye Hua asked and answered himself:
"So we assume that there is a 'universal algorithm' that can reduce all np problems to p-type problems. This is the p=np? problem. We don't even need to figure out what this 'universal algorithm' is, as long as we can prove or
If you prove it false, you can win a million-dollar prize."
Immediately he looked at the students: "At the same time, we will find that there is a small category of np problems that are obviously much more difficult than p-type problems. In the sense that these problems are the least likely to become p-type problems,
, and these problems also have one thing in common. Once it is proved that any of the problems has a superior algorithm that can be reduced to a p-type problem, then 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 type of problem is referred to as np-c, which is also an np-complete problem."
When Ye Hua explained it to this point, everyone could understand it very well, but the next questions were not so friendly to them.
"NPC is obviously more difficult than P-type problems. Let's take an example that is close to our lives. For example, a Meituan delivery boy lives at point a and wants to deliver food to n places. The distance between n places is
They are all known. So how can this takeaway boy visit every location and finally return home, ensuring that the distance he takes is the shortest?"
At this point, Ye Hua paused, picked up the water cup and took a sip to moisten his throat. The eight students frowned and thought. Among them, Ning Jie, who was the most talented in mathematics, was also full of doubts.
After a while, no one took the initiative to answer. As expected, Ye Hua said: "The question is, the delivery boy must first face how many possible walking routes there are, and how to describe them mathematically?"
The students all looked at Ye Hua, who said: "Obviously, the final result is the factorial o(n!) of n. So you can see that the complexity of this problem is much larger than the problems described before.
Because o(n!)≈√2π(n/e)^n, this number is much larger than the exponent with the base constant.”
Ye Hua immediately turned around and swiped on the blackboard simulated on the floating screen: "For example, the factorial of 19 seems to be a small number, but let's give it a formula: 19! ≈ 1.21x10^17. This number is so big that even
Using the most powerful classical computer now, assuming that it can queue 1 million times per second, it will still take about three thousand years. Therefore, if the delivery boy delivers so many goods every day, in theory, he just wants to find the best route.
It’s possible.”
"But students, please note that the difficulty and simplicity here represent a trend. When n is very small, the calculation amount of the human brain can be calculated quickly. For example, Sudoku, even elementary school students can calculate 3x3 Sudoku.
But students, let me give you a 100x100 to try? For example, a 100x100 square grid, give a few numbers from 1 to 100 as clues, and then ask to fill in the rest and make sure that they are 1 to 100 horizontally and vertically. This question
Even if you use the most powerful computer in the world today, you can’t figure it out quickly.”
"So obviously, this question is also an NPC question. Have you ever played Minesweeper? Are there any mini games like Tetris? They are also NPC questions." At this point, this knowledge point was almost explained. Ye Hua finally said:
"So if it can be proved that p=np, it will be a great contribution to all mankind. For example, the protein folding complexity in the human body is an npc problem. Once it is proved that it is p... why are you laughing?"
Seeing Liu Ling's smile, Ye Hua gave her a stern look. He could tell that this little girl was the naughtiest among the eight students.
He coughed slightly and continued the previous topic: "...So as long as it is proved that it is a p-type problem, many diseases can be easily solved, including cancer and AIDS. But it is quite difficult to prove that p=np
It’s not easy, because firstly proving that p=np is a problem, right? Then the problem comes, it itself is an NPC problem..."
As if I felt the deep malice and full hostility brought by this question, this question is indeed a show, and it is worthy of being the first of the world's seven major mathematical problems that have left mathematicians all over the world at a loss.
