NP问题：完全(NP Complete,NPC)问题是指如许一类NP问题，所有的NP问题都能够用多项式时间划回到他们中的一个。所以显然NP完全的问题具有如下性量：它能够在多项式时间内求解，当且仅当所有的其他的NP－完全问题也能够在多项式时间内求解。
起首需要介绍P(Polynomial,多项式)问题。P问题是能够在多项式时间内被确定机(凡是意义的计算机)处理的问题。NP(Non-Deterministic Polynomial, 非确定多项式)问题,是指能够在多项式时间内被非确定机(他能够猜,他老是能猜到最能称心你需要的那种抉择,假设你让他处理n皇后问题,他只要猜n次就能完成----每次都是那么幸运)处理的问题。
那里有一个闻名的问题----千禧难题之首,是说P问题能否等于NP问题,也便是否所有在非确定机上多项式可解的问题都能在确定机上用多项式时间求解。
如许一来,只要我们找到一个NPC问题的多项式解,所有的NP问题都能够多项式时间内划回成那个NPC问题,再用多项式时间处理,如许NP就等于P了。
换一种说法,假设一个问题的复杂度是该问题的一个实例规模n的多项式函数，则那种能够在多项式时间内处理的问题属于P类问题。通俗地称所有复杂度为多项式时间的问题为易解的问题类，不然为难解的问题。
有些问题很难找到多项式时间的算法（或许底子不存在），例如“找出无向图中哈密顿回路”问题。
但假设给了该问题的一个谜底，能够在多项式时间内揣度那个谜底能否准确。例如说关于哈密顿回路问题，给一个肆意的回路，很随便揣度它能否是哈密顿回路（只要看是不是所有的顶点都在回路中就能够了）。那里给出NP问题的另一个定义,那种能够在多项式时间内验证一个解能否准确的问题称为NP问题，亦称为验证问题类。
简单的说，存在多项式时间的算法的一类问题，称之为P类问题；而像梵塔问题，推销员游览问题等问题，至今没有找到多项式时间算法解的一类问题，称之为NP问题。同时，P类问题是NP问题的一个子集。
NP完全问题：NP完全问题，是世界七大数学难题之一。
NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂水平的非确定性问题。简单的写法是 NP=P？，问题就在那个问号上，到底是NP等于P，仍是NP不等于P。
NP就是Non-deterministic Polynomial的问题，也便是多项式复杂水平的非确定性问题。
而假设任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么那个NP问题就称为NP完全问题（Non-deterministic Polynomial complete problem）。NP完全问题也喊做NPC问题。
以上来自百度。