P. Summary of NP, NPC, NP hard and other issues

0. Concept

• P Problem: For any input size n, The problem can be in n Is solved in polynomial time ;
• NP(Non-deterministic Polynomial) Problem: A problem that can verify a solution in polynomial time ;
• NPC(Non-deterministic Polynomial Complete) Problem: Two conditions are satisfied :
  • It's a NP problem
  • be-all NP The problem can be reduced to it
• NP-hard Problem: Satisfy NPC The second part of the question 2 strip , But it is not necessary to meet the requirements of article 1 strip .（NP-Hard The problem is better than NPC The scope of the problem is wide ）

1. P Problem

If a problem can be solved by an algorithm in polynomial time , So this question belongs to P problem , That is, the time complexity of the algorithm is polynomial . such as n Find the maximum value in the middle of the number , perhaps n Sort by number .

2. NP Problem

NP Another definition of a problem is that a solution can be guessed in polynomial time , For example, find out whether there is a line less than... From the starting point to the end point in the graph 100 A route per unit length , Pick any one , If the calculated path is less than 100, So I guess a solution , That is to say, if you are lucky enough, you can solve this problem in polynomial time . Of course, the premise of guessing is that there is a solution to the problem .

Obviously , be-all P All kinds of problems are NP problem , It can be solved in polynomial time , It must be possible to verify a solution polynomially .（NP Is it equal to P It seems that this problem has not been settled yet .）

The famous NP Class problem ： Traveler selling problem (TSP).
There is a salesman , Need to go to n   A city sells goods , He wants to find one that contains all n The ring road of a city , This loop path is less than a . We know that if this problem is simply enumerated by enumeration, there will be ( n − 1 ) ! Kind of , It's not a polynomial time algorithm anymore ( notes ： Factorial algorithm is more complex than polynomial ). Then what shall I do? ？ We can guess , Suppose I have a good character , After several guesses, I guessed one less than the length a The path of , well , I got a path less than a The loop of , Problem solved , All's well that ends well . But , I can't guess so accurately every time , Maybe I'll guess all the species ？ So we say , This is a NP Class problem .

So this leads to a millennium issue of this kind of discussion ： whether NP Class problem =P Class problem ？ That is, whether all problems can be verified to get the correct solution in polynomial time , Are all problems with polynomial time algorithms ？ If this problem is solved , Isn't that all NP All problems can be solved by computer .

3. NPC Problem

There is one. NP problem , Make all this class NP Problems can be formulated in polynomial time (Polynomial-time Reducibility) by NPC problem . According to the transitivity of the protocol , Yes NP Problems are regulated layer by layer , Finally, we can get a sufficiently generalized NP problem , namely NPC problem .

What is reduction (Reducibility)

A problem A It can be reduced to a problem B The meaning is , You can use questions B To solve the problem A.（ My personal feeling is that , problem A yes B A special case of .） Standardization is defined as , If we can find a law of change , To any one A Program input , Can be transformed into according to this law B Program input , Make the output of the two programs the same , So the question A It can be reduced to a problem B .

For example, the problem of solving a linear equation in one variable can be reduced to solving a quadratic equation in one variable , That is, the coefficient of the corresponding term can be kept constant , The coefficient of the quadratic term is 0, take A The input parameters of the problem are brought into B Problem solver to solve . in addition , Reduction is also transitive ,A It can be reduced to B,B It can be reduced to C, that A It can also be reduced to C.

4. NP-hard problem

NP-hard problem, NP(Non-deterministic Polynomial)

5. Other

5.1 What is time complexity （Time Complexity）

Time complexity It doesn't mean how long it takes a program to solve a problem , It is When the scale of the problem expands , How fast does the length of time required by the program grow . in other words , For computers that process data at high speed , The efficiency of processing a particular data cannot measure the quality of a program , But we should see that when the scale of this data becomes hundreds of times , Is the running time of the program the same , Or hundreds of times slower , Or tens of thousands of times slower . No matter how big the data is , The processing time is always so much , Let's say it's a good program , have O(1) Time complexity of , Also known as constant level complexity ; How big the data has become , How long does it take , The time complexity of this program is O(n), Like looking for n Maximum number ; And it's like bubble sorting 、 Insert sort, etc , Data expansion 2 times , Time slows down 4 Times , Belong to Complexity . There are also algorithms for exhausting classes , The length of time required increases in geometric order , This is it. Exponential complexity of , even to the extent that O(n!) The factorial complexity of . No existence Complexity , Because the one in front “2” It's a coefficient , It doesn't affect the time growth of the whole program at all . similarly , The complexity of that is ​​​​​​​​​​ Complexity . therefore , We will say , One It's more efficient than Low efficiency , Although in n When I was very young , The former is better than the latter , But the latter grows slowly with the size of the data , Final It's going to be much more complicated than . We also say , The complexity of is less than Complexity .
Easy to see , The previous types of complexity are divided into two levels , The latter is much more complex than the former in any case ; One is ,, etc. , Let's call this Polynomial level complexity , Because of its size n At the base of the number ; The other is and Type complexity , It is non polynomial , The complexity of the computer is often unbearable . When we're solving a problem , The algorithm we choose usually needs to be polynomial level , Non polynomial complexity takes too much time , It tends to time out , Unless the data scale is very small .

O() and o() Represent the Same order infinitesimal and higher order infinitesimal .
a,b It's all infinitesimal ．
If b/a The limit of is equal to 0, Just say b It's better than a Infinitesimal of higher order , Write it down as b=o(a).
If b/a The limit of is equal to c(c≠0), Just say b And a It's infinitesimal of the same order , Write it down as b=O(a)

5.2 What is a heuristic algorithm

Heuristic algorithms are generally used to solve NP-hard problem , among NP Is a nondeterministic polynomial .

for example , Famous salesman travel problem （Travel Saleman Problem or TSP）： Suppose a salesman needs to start from Nanjing , Passing through Guangzhou , Beijing , Shanghai ,…, etc. n Cities , Finally, I returned to Hong Kong . There are direct flights between any two cities , But the ticket prices vary . Suppose the company only reimburses C Yuan , Ask if there is a schedule , So that he can traverse all the cities , And the total toll is less than C？

The problem of salesman travel is obviously NP Of . Because if you give an arbitrary itinerary , It's easy to figure out the total cost of the trip . however , If you want to know that the total cost of a road is less than C Whether the stroke of exists , In the worst case , All possible travel arrangements must be checked .

Heuristic algorithm is proposed relative to optimization algorithm , It is an algorithm constructed based on intuition or experience , At acceptable cost （ Time and space ） A feasible solution of the combinatorial optimization problem to be solved is given .

 

Reference material

[1]  What is the NP-hard_ A handsome man like an immortal -CSDN Blog _np-hard

[2] What is? P problem 、NP Questions and NPC problem | Matrix67: The Aha Moments