当前位置:网站首页>Detailed explanation of P problem, NP problem, NPC problem and NP hard problem
Detailed explanation of P problem, NP problem, NPC problem and NP hard problem
2022-07-06 06:12:00 【Zhan Miao】
1. polynomial time (Polynomial time)
Time complexity doesn't mean how long it takes a program to solve a problem , But when the scale of the problem handled by the program expands , The length of time required by the program corresponds to how fast it grows . in other words , For a program , Its efficiency in processing a specific data cannot measure the quality of the 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 , Like looking for n The time complexity of this program is O(n), Is linear complexity , And it's like bubble sorting 、 Insert sort, etc , Data expansion 2 times , Time slows down 4 Times , The time complexity is , The complexity is square . 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 The factorial complexity of .
Combine the function to increase the speed and the actual operation effect of the algorithm , Polynomial time algorithm can be regarded as efficient algorithm or practical algorithm , Exponential time algorithm is not practical .
2. Deterministic algorithm and non deterministic algorithm
2.1. Deterministic algorithms
set up A Is to solve the problem B A solution algorithm of , During the whole execution of the algorithm , A definite solution can be obtained at each step , Such an algorithm is a deterministic algorithm .
2.2. Nondeterministic algorithm
set up A Is to solve the problem B A solution algorithm of , It divides the problem into two parts , They are guess stage and verification stage , among
- Guess stage : At this stage , A specific input instance of the problem x Generate an arbitrary string y, At every run of the algorithm ,y The value of may be different , therefore , Guess works in an uncertain form .
- Validation phase : At this stage , Use a deterministic algorithm ( In a limited time ) verification .① Check for y Is it a suitable form , If not , Then the algorithm stops and gets no;② If y Is the appropriate form , Then verify whether it is the solution of the problem , If it is , Then the algorithm stops and gets yes, Otherwise, the algorithm stops and gets no. It is to verify the correctness of the guessed solution .
3. Statute / reduction
problem A It can be reduced to a problem B, be called “ problem A It can be stipulated as a problem B”, It can be understood as a problem B The solution must be the problem A Solution , Therefore, it is necessary to solve the problem A It won't be difficult to solve B. This shows the problem B The time complexity must be greater than or equal to the problem A.
Now there are two questions : Solving a linear equation of one variable and solving a quadratic equation of one variable . So let's say , The former can be stipulated as the latter , That is to say, if you know how to solve a quadratic equation with one variable, you can solve it . We can write two programs corresponding to two problems , So we can find one “ The rules ”, According to this rule, change the input data of the program for solving linear equation of one variable , It is used in the program of solving quadratic equation of one variable , Two programs always get the same results . The rule is : The coefficients of the corresponding terms of the two equations remain unchanged , The coefficient of quadratic term of quadratic equation of one variable is 0.
From the definition of the statute, we can see , One problem is regulated as another problem , Time complexity has increased , The scope of application of the problem has also increased . Through constant regulation of certain issues , We can keep looking for more complex , But it's less complex to replace it with a wider range of algorithms , But it can only be used for a very small class of problems . There is such a NP problem , be-all NP The problem can be reduced to it . let me put it another way , As long as the problem is solved , So all NP All the problems have been solved . The existence of this kind of problem is unbelievable , And even more incredible , There is more than one such problem , It has a lot of , It's a kind of problem . This kind of problem is legendary NPC problem , That is to say NP- Problem completely .
4. P Class problem 、NP Class problem 、NPC problem 、NP Difficult problem
P Class problem : Problems that can be solved in polynomial time .
NP Class problem : In polynomial time “ Verifiable ” The problem of . in other words , We can't decide whether the problem is solved or not , Instead, guess a solution to prove whether the solution is correct in polynomial time . That is, the guessing process of the problem is uncertain , The verification of one of its solutions can be completed in polynomial time .P Class problems belong to NP problem , but NP Class problems do not necessarily belong to P Class problem .
NPC problem : There is such a NP problem , be-all NP The problem can be reduced to it . let me put it another way , As long as the problem is solved , So all NP All the problems have been solved . Its definition should meet 2 Conditions :
- It's a NP problem ;
- all NP Problems can be regulated to it .
NP Difficult problem :NP-Hard The problem is such a problem , It meets the NPC The second article of the definition of the problem, but it does not have to meet the first article ( That is to say ,NP-Hard The problem is better than NPC The scope of the problem is wide ,NP-Hard The problem is not limited to NP), That all the NP Problems can be reduced to it , But he is not necessarily a NP problem .NP-Hard The problem is also difficult to find the algorithm of polynomials , But it's not part of our research , Because it doesn't have to be NP problem . Even if NPC The problem found a polynomial level algorithm ,NP-Hard The problem may still not be able to get a polynomial algorithm . in fact , because NP-Hard Relaxed restrictions , It will be possible than all NPC The time complexity of the problem is higher, so it is more difficult to solve .
The relationship between the above four issues is shown in the figure below :
reference
Combinatorial optimization _ Zhejiang University _ University of China MOOC( MOOC )
边栏推荐
猜你喜欢
使用Nacos管理配置
[web security] nodejs prototype chain pollution analysis
LeetCode 729. 我的日程安排表 I
LAN communication process in the same network segment
MySQL之数据类型
Raised a kitten
Expose the serial fraudster Liu Qing in the currency circle, and default hundreds of millions of Cheng Laolai
LeetCode 1200. 最小绝对差
[eolink] PC client installation
Idea new UI usage
随机推荐
【Postman】Collections配置运行过程
Buuctf-[[gwctf 2019] I have a database (xiaoyute detailed explanation)
通过修改style设置打印页样式
联合索引的左匹配原则
Accélération de la lecture vidéo de l'entreprise
Function of activation function
Amazon Engineer: eight important experiences I learned in my career
Cognitive introspection
如何在业务代码中使用 ThinkPHP5.1 封装的容器内反射方法
Expose the serial fraudster Liu Qing in the currency circle, and default hundreds of millions of Cheng Laolai
Digital triangle model acwing 1015 Picking flowers
Manhattan distance and Manhattan rectangle - print back font matrix
Bit operation rules
《卓有成效的管理者》读书笔记
SQLMAP使用教程(三)实战技巧二
J'ai un chaton.
Réflexions sur la sécurité des données (réimpression)
【C语言】qsort函数
[C language] qsort function
Leaflet map