P问题是可以由具有多项式级复杂度的算法求解的问题，NP问题是可以用多项式级算法验证一个解的问题，NPC（NP-complete）问题是所有NP问题都可以化归为它（NPC）的问题（NPC ⊆ NP），存在不止一个NPC问题，如果人们找到一个NPC问题的（多项式级）解，（由问题的规约性质可知）所有的NP问题都可得到多项式级解，也即P==NP（P等价于NP），但由于NPC问题太难，人们猜测其没有可以验证其一个解的多项式级算法，所以人们普遍认为P!=NP。

NPC问题：

逻辑电路问题

这是有严格证明的。它显然属于NP问题，并且可以直接证明所有的NP问题都可以约化到它（不要以为NP问题有无穷多个将给证明造成不可逾越的困难）。证明过程相当复杂，其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些 0和1的运算），因此对于一个NP问题来说，问题转化为了求出满足结果为True的一个输入（即一个可行解）。

Hamilton回路

问题是这样的：给你一个图，问你能否找到一条经过每个顶点一次且恰好一次（不遗漏也不重复）最后又走回来的路（满足这个条件的路径叫做Hamilton回路）。