(This chapter is for everyone to look at as a scholar, if you don't understand it, it's better to be the protagonist, this chapter is to pave the way for the future biological genetic engineering, everyone will know after reading it, and there will be no such persuasion chapters in the later updates, and they will all be written with tears in mind...... o(╥﹏╥)o）

——

Ye Hua looked at several students and smiled: "As the first of the seven problems of millennial mathematics, "P=NP?" No one has been able to prove or falsify the problem so far, and if any of you can solve this problem in the future, you can immediately go to the Clay Institute of Mathematics in the United States and receive a $1,000,000 bounty, which is still valid until the millennium. ”

"It is not only the first of the world's seven major mathematical problems, but at the same time, it is the easiest mathematical problem to understand among the seven problems, in fact, it is a problem to do Sudoku, which was born in 1971 and is a mathematical problem born in the field of theoretical computers."

Teaching is a kind of teaching 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, in life, how do you measure a problem? Is it simple or complex? Or is it easy or difficult? Ye Hua paced in class, sometimes using his spare eyes to scan whether several students were listening carefully, no small movements could escape Principal Ye's eyes, and these students were quite well-behaved during class, including Liu Lingshuang, who usually likes to make trouble.

After a moment, he asked himself: "It doesn't seem that there is a specific quantitative standard, and the questions will vary from person to person." But computers are different, the computational efficiency of computers is a fixed value, and there is no intelligence quotient. ”

"For example, if a computer displays from 1 to 10 and from 1 to 1000, it will take 100 times longer for the latter problem, which is more difficult than the previous one."

"For a computer, measure the simplicity or difficulty of a problem, and see how many times or steps to solve the problem, because the efficiency is equivalent to the time and the number of steps in a certain situation, and giving a definition is called time complexity, and the smaller the time complexity, the less the problem, the simpler the problem. But what else do you have to consider in practice? ”

After speaking, Ye Hua looked at a few of them, and after a while, Liu Lingshuang said, "You have to consider the space occupied by the computer." ”

"The answer is absolutely correct."

The hacker girl is praised for her secret joy, and the computer is the heroine's forte.

Ye Hua gave her a praising look, which was a reward, and then said: "Put aside the space problem, let's talk about the time problem today, for example......"

Nothing is easier to understand than the classic "lift a chestnut".

"A question, now I give you n numbers, and ask to choose the largest number among them, how many steps does it take? Who knows? ”

As soon as the words fell, the youngest Ning Jie quickly replied: "N-1 step." ”

"Correct!"

Ye Hua nodded, the little mathematical genius Ning Jie answered so quickly because he expected, and called up the floating screen to list a string of numbers: "The method is actually very simple, first compare the first two, take the largest number and compare it with the third number, and then take the largest number and compare it with the fourth, and so on, take n numbers and compare n-1 times." ”

"The second question is still given n numbers, but this question requires the number of n numbers to be sorted from large to small, so how many steps does it take?"

Ning Jie said again without thinking: "N(n-1)/2 steps are required." ”

Ye Hua nodded again: "The answer is correct." Ning Jie: Can you tell us about the calculation process with other students? ”

Ning Jie immediately replied: "It takes n-1 steps to select the largest number with the method just now, and then to select the largest number among all the remaining numbers with n-2 steps, and so on is (n-1)+(n-2)+(n-3)+...... The answer that goes all the way up to the end is n(n-1)/2. ”

Liu Lingshuang quickly understood it when she saw it, isn't this the "bubbling method" in computer programming, the hacker girl naturally understands it at a glance, in fact, these are simple questions, and the eight students present can quickly understand it.

Ye Hua continued: "Obviously, with the increase of n, the difficulty of the sorting problem is higher than the difficulty of choosing the largest number before. n-1 When this n is very large, -1 can be omitted, whether there is no effect, the order of magnitude is determined by n, the second question time of the order of magnitude is determined by n^2, others can also be omitted, including coefficients. ”

Speaking of this, Ye Hua called up a large floating screen that simulated a blackboard, replaced chalk with his fingers, dotted white on the color board, and then listed the formulas on the panel: "Represented by the progressive symbol O, the computational amount of the first question is represented as O(n), and the second question is represented as O(n^2). A comparison of the two questions shows that O(n^2) is more difficult as n increases, which is understandable because n^2 is larger than n. ”

Ye Hua continued to write: "n, n^2, n^3, etc., or their combinations, are called polynomials, and this kind of problem is "P=NP?" Questions". Is there a more difficult question then? Of course there are, such as the problem of prime numbers. ”

Saying that, Ye Hua looked back at the students: "Is a natural number a prime number?" How many steps does it take to solve it? The stupid method is to divide one by one, starting from 1 to divide √a, so at most √ a step is used, and the full description is: Is a natural number a of n digits a prime number? ”

Ye Hua, who completely took on the role of lecturer, immediately turned around and continued to list the formulas on the floating screen: "The decimal number of n digits can be represented: 10^n-10^(n-1), then obviously the prime number problem is: O(√10^2), even if it is a binary number: O(√2^n), students, with the increase of the number of digits n, has the prime number problem risen exponentially? It's a terrifying upward trend. ”

All of the above problems have one thing in common, no matter how difficult or not, as long as you give an answer to verify, it will seem much easier, for example: a is not a prime number, because it is divisible by this number b, then it is enough to check it, and it can be verified in polynomial time. Then all these problems are NP problems. ”

Ye Hua looked around at the eight students and saw that there was no doubt or confusion in their eyes, obviously they all understood, and they were very satisfied with their performance.

"N stands for non-deterministic, the standard definition of P and NP is related to Turing machine, 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 the two, pay attention. Does that mean that NP questions are more difficult than P questions? The answer is no, because P questions are NP questions, which should also be noted. ”

Ye Hua paced in front of the students again, and said in an orderly manner: "In mathematics or in the field of computers, the difficulty of a problem depends largely on the calculation method, the computer is the algorithm, and the algorithm is the soul of the computer. Even if you do math problems, some methods of the same problem are simple and fast, and it may be a problem that is missing an auxiliary line. ”

"The previous talks are all ways to die, just achieve the goal. The term in the computer is called 'bubbling method', and its complexity is O(n^2), and the complexity can be reduced by developing superior algorithms, for example, the complexity of the quick-sort method is O(nlogn), which is obviously smaller than n^2, so in the computer field, it is easy to see whether its algorithm is superior or not for the difficulty of a problem. ”

"Then it's not hard to understand that the purpose of studying every computer's algorithm is to reduce NP problems to P problems. But there are so many questions, to find the Year of the Monkey and the Month of the Horse? So, since NP problems have one thing in common, i.e., they can all be verified in polynomial time, will there be another thing in common? ”

Ye Hua asked and answered:

"So let's assume that there is a 'one-size-fits-all algorithm' that reduces all NP problems to P-class problems, which is "P=NP?" Issue. You don't even need to figure out what this 'universal algorithm' is, as long as it can be proved or falsified, you can win a million jackpots. ”

He immediately looked at the students: "At the same time, we will find that there is a small class of problems in the NP problem, which is obviously much more difficult than the P problem, and it feels that these problems are the least likely to become P problems, and these problems also have one thing in common, once it is proved that any one of the problems has a superior algorithm that can be reduced to a P problem, then the other problems can also be reduced to a P problem, in other words, as long as one of them is proved to belong to P, it is P=NP." Then this sub-category of problems is referred to as NP-C, which is the NP complete problem. ”

When Ye Hua explained this, everyone could understand it very well, but the next question was not so friendly to them.

"NPCs are obviously more difficult than P-type problems, or for example, close to our lives, for example, a Meituan delivery guy, his family lives in point A, and he wants to go to n places to deliver takeaways, and the distance between the two and two of n locations is known. So how does this takeaway guy go to every location and finally return home to ensure that the distance he walks is the shortest? ”

Speaking of this, Ye Hua paused, picked up the water cup and took a sip to moisten his throat, and the eight students frowned and thought, among which Ning Jie, who had the best mathematical talent, was also suspicious.

After a while, no one took the initiative to answer, and as expected, Ye Hua said: "This topic is, how many walking routes does the takeaway brother have to face first, and how to describe it 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 is much bigger than the problem I talked about before, because O(n!) ≈√2π(n/e)^n, this number is much larger than an exponent with a constant base. ”

Ye Hua immediately turned around and slid on the blackboard simulated by the floating screen: "The column is like the factorial of 19, it seems that this number is not big, but the column formula: 19!≈1.21×10^17, this number is so large that even if the most powerful classical computer is used to assume that he can arrange 1 million times per second, it will take about 3,000 years." Therefore, the takeaway brother delivers so many goods every day, theoretically it is impossible for him to find the best route. ”

"But students pay attention, the difficulty and simplicity here represent a trend, when n is very small, the amount of calculation of the human brain can also be quickly calculated, such as Sudoku, 3×3 Sudoku that elementary school students can calculate, but students, I will give you a 100×100 to try? For example, 100×100 squares, give a few 1~100 numbers as clues, and then ask to fill the rest of each and ensure that the horizontal and vertical are 1~100, this problem can not be quickly found even with the best computer in the world today. ”

"So obviously, this question is also an NPC problem, have you played these mini-games such as minesweeper and Tetris? They are also NPC issues. Speaking of which, this knowledge point is almost explained, Ye Hua finally said:

"So if it can be proved that P=NP, then the contribution to all mankind will be great, for example, the complexity of protein folding in the human body is an NPC problem, once it is proved that it is a P ...... What laugh at what laughs? ”

Seeing Liu Lingshuang sneering, Ye Hua pretended to glare at her, this little girl, he could see that she was the most skinny among the eight students.

He coughed lightly, and then continued with the previous topic: "...... Therefore, as long as it is proved that it is a P problem, many diseases can be solved, such as cancer and AIDS. But it's not easy to prove P=NP, because first of all, "proving P=NP" is a problem, right? So here's the problem, it's an NPC problem in itself......"

As if feeling the deep malice and hostility brought about by this question, this question is indeed a show, and it deserves to be the first of the world's seven major mathematical problems that have so far left mathematicians all over the world helpless.

……