P问题、NP问题、NPC问题、NPH问题概述

P问题

如果一个问题可以找到一个能在多项式的时间里解决该问题的算法，这个问题就属于P问题。
           

NP问题

可以在多项式的时间里验证一个解的问题。
所有的P问题都是NP问题，即能在多项式时间内解决一个问题，必然能在多项式时间里验证一个问题的解。
           

NPC问题

首先必须是一个NP问题，然后所有的NP问题都可以约化到该问题。
约化：问题A可以约化为问题B，即可以用问题B的解法解决问题A，解决问题B的时间复杂度大于等于解决A的时间复杂度。
约化具有传递性，问题A可以约化为问题B，问题B可以约化为问题C，则问题A一定可以约化为问题C。
约化的过程需要在多项式时间内完成。
目前被证明是NPC问题的有很多，任何一个找到了多项式时间复杂度的算法，所有的NP问题都可以被完美解决。
           

NPH问题

所有的NP\NPC问题都能在多项式时间复杂度内约化到的问题，但该问题不一定是NP问题。
           

参考文献

[1]P问题、NP问题和NPC问题

[2]P问题、NP问题、NP完全问题和NP难问题

[3]算法中的P问题、NP问题、NP完全问题和NP难问题

[4]谈“P=NP?”

[5]假如P=NP，世界将会怎样？

[6]【算法】P问题 NP问题 NPC问题 NPH问题的定义与理解