最近看了有关NP问题相关的一些内容，在网上查找了一些资料，进行了一些整理，但是由于接触尚浅，如果其中内容有错误或者模糊，欢迎指正教导，非常感谢！
内容均由笔者整理自网络，引自百度百科、csdn论坛以及相关博客等。
（一）首先涉及到的基本概念有：
- （1）确定性算法（Determinism）： 设A是问题Π的一个解决算法，在算法的整个执行过程中，每一步都能得到一个确定的解，这样的算法就是确定性算法。
- （2）非确定性算法（Nondeterminism）：设A是求解问题Π的一个算法，它将问题分解成两部分，分别为猜测阶段和验证阶段，其中
- 猜测阶段：在这个阶段，对问题的输入实例产生一个任意字符串y，在算法的每一次运行时，串y的值可能不同，因此，猜测以一种非确定的形式工作。
- 验证阶段：在这个阶段，用一个确定性算法（有限时间内）验证：① 检查在猜测阶段产生的串y是否是合适的形式，如果不是，则算法停下来并得到no；② 如果串y是合适的形式，则验证它是否是问题的解，如果是，则算法停下来并得到yes，否则算法停下来并得到no。它是验证所猜测的解的正确性。
（二）P问题
P(Polynomial,多项式)问题，P问题是可以在多项式时间内被解决的问题。
（三）NP问题
NP类问题（Nondeterminism Polynomial）：在多项式时间内“可验证”的问题。也就是说，不能判定这个问题到底有没有解，而是猜出一个解来在多项式时间内证明这个解是否正确。即该问题的猜测过程是不确定的，而对其某一个解的验证则能够在多项式时间内完成。直白的说，就是可以在多项式的时间里猜出一个解的问题。
（四）NPC问题
如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题（Non-deterministic Polynomial complete problem）。NP完全问题也叫做NPC问题。
NPC（Nondeterminism Polynomial complete）：存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。其定义要满足2个条件：
首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。
要证明NPC问题的思路就是： 先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它。
※注：什么是约化||规约：简单的说，问题A可以约化为问题B，就可以理解为：问题B的解就一定是问题A的解。因此可以理解为，解决A不会难于解决B。
《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以规约为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为0。
NP完全问题(NP-C问题)，是世界七大数学难题之一。
举例来说（例子来源于百度百科），在一个周六的晚上，你参加了一个盛大的晚会。由于感到局促不安，你想知道这一大厅中是否有你已经认识的人。晚会的举办者向你提议说，你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟，你就能向那里扫视，并且发现举办者是正确的。然而，如果没有这样的暗示，你就必须环顾整个大厅，一个个地审视每一个人，看是否有你认识的人。
生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是，如果某人告诉你，数13,717,421可以写成两个较小的数的乘积，你可能不知道是否应该相信他，但是如果他告诉你他可以因式分解为3607乘上3803，那么你就可以用一个袖珍计算器容易验证这是对的。人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们于是就猜想，是否这类问题，存在一个确定性算法，可以在多项式时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。 不管我们编写程序是否灵巧，判定一个答案是可以很快利用内部知识来验证，还是没有这样的提示而需要花费大量时间来求解，被看作逻辑和计算机科学中最突出的问题之一。
五）NP-Hard问题：
NP-Hard问题又叫NP难问题，他不是一个NP问题，然后所有的NPC问题都可以在多项式时间内转化为他的话，我们就叫他NPH（hard）问题。
最具代表性的NP-Hard问题：
问题1：
TSP。著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，…，等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销 C 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？
推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排！ 这将是个天文数字。
旅行推销员问题是数图论中最著名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。
问题2：背袋问题（甲）
有物体 n 个，各重 w1,w2,…,wn，今欲将它们分为二袋， 试问如何分法可使两袋之重要最为接近。 （不妨假定 wi 皆为正整数，这并未失去一般性。)
问题3：包装问题
有 n 个各别重量小于 1 公斤的物品及足够可以装 1 公斤东西的盒子，今将物品装于盒子之中，多个物品可装于一盒，但任何一盒不得重于 1 公斤，试求最小的盒子数。
问题4：舞伴问题
今有 n 个男孩子与 n 个女孩子参加舞会，每个男孩与女孩均交给主持一个名单， 写上他（她）中意的舞伴（至少一人，但可以多于一人）。试问主持人在收到名单后，是否可以分成 n 对，使每人均得到他（她）所喜欢的舞伴。
问题5：库存问题
某仓库有 D 个存仓，排成一列，今有 n 批货物，各可占有一个或多个存仓，并已知各批物品存入与提出之日期。试问可否将各货物存入库时不发生存仓不够的困难且同一批货物若需一个以上存仓时，其存仓必须相邻。
问题6：
（甲） 给定一 n 位正整数 a，试问其是否为质数？
（乙） 给定一 n 位正整数 a，试问是否存在 m,n >1 且 a=mn？
问题7：分丛问题
已知空间 n 个点，并假定各点之间之距离为正整数，又给定两正整数 K 与 B， 问是否可将此 n 点分成小于 K 个不重合的子集，使得在同一子集内之任意二点距离均不大于 B？
目前求解NP难问题的常见方法
（1） 特殊情形：仔细分析所遇到的NP完全问题，研究具体实例的特殊性，考虑是否必须在最一般的意义来解此问题。也许可利用具体实例的特殊性，在特殊条件下解此问题。许多NP完全问题在特殊情形下可以找到多项式时间算法。例如求图G的最大团问题（典型描述，给定一个图G，要求G的最大团，团是指G的一个完全子团，该子团不包含在任何其他的完全子图当中，最大团指其中包含顶点最多的团）是NP完全问题，而在图G是平面图的情形下，该问题是多项式时间可解的。
（2） 动态规划和分枝限界方法：对于许多NP完全问题来说，用动态规划和分枝限界方法常可得到较高的解题效率。
（3） 概率分析：对于许多NP完全问题，其困难实例出现的概率很小，因此对这类NP完全问题常可设计出平均性能很好的算法。
（4） 近似算法：通常可以设计出解NP完全问题的多项式时间近似算法，以近似解来代替最优解。