一、P（Polynomial）

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

二、NP

NP 问题是指可以在多项式的时间里验证一个解的问题，所有的 P 类问题都是 NP 问题。

三、NPC

同时满足下面两个条件的问题就是 NPC 问题。首先，它得是一个 NP 问题；然后，所有的 NP 问题都可以约化到它。证明一个问题是 NPC 问题也很简单。先证明它至少是一个 NP 问题，再证明其中一个已知的 NPC 问题能约化到它，这样就可以说它是 NPC 问题了。

四、已知 NPC 问题

逻辑电路问题、Hamilton 回路、TSP（旅行商问题）等