一、P(Polynomial)

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

二、NP

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

三、NPC

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

四、已知 NPC 问题

逻辑电路问题、Hamilton 回路、TSP(旅行商问题)等