Understanding of p-type problems, NP problems, NPC problems, and NP hard problems in natural computing

Only for personal learning and sorting ：

1.P Class problem

P Class problem is a kind of problem that can use Deterministic algorithms stay Polynomial time Solve the decision problem .

2.NP problem

NP Class problem is a kind of problem that can use Uncertainty algorithm stay Polynomial time Solve the decision problem .

 

P Class questions and NP Simple problem memory . Below NPC Questions and NP-hard Problems in the form of sets may be better understood and remembered , Please refer to the set relationship, which may be easier to understand .

 

3.NPC problem

If a question D Belong to NPC problem , Then we should satisfy ：

（1） problem D Belong to NP Class problem （NPC The problem belongs to NP Class problem , namely NPC The problem is NP A subset of class problems );

   (2)   NP Any problem in this kind of problem can be transformed into NPC problem （ It can be understood as NP Class problem Any element of can transformation To NPC This subset of problems ）.

4.NP-hard problem

 NP-Hard problem , Satisfy NPC Problem satisfied （2） But it doesn't have to be satisfied （1）.

（ That is to say, all NP Problems can be transformed into NP-hard problem , however NP-hard It doesn't necessarily belong to NP problem .NPC The problem is NP-hard Subset of problems ）

 

The above set represents images for reference , link ：https://blog.csdn.net/qq_21768483/article/details/80430590