1 .在p类问题和NP类问题NP-Hard问题之前，可以找到并解决p类问题和NP类问题P类问题：多项式时间复杂度算法，通过验证结果的正确性例如，可以自由获取一个结果，在多项式时间内验证其结果是否正确，但不知道求解其结果的时间的复杂性。 p类问题一定是NP类问题，但NP类问题不一定能找到多项式时间复杂度的算法来解决。 因此，人们关心的是是否所有的NP问题都是p问题，即是否存在P=NP (情报学的顶点问题)
到目前为止这个问题还“吃不了”。 但是，一般的趋势是，P=NP不成立。 也就是说，很多人相信存在至少存在一个不能具有多项式级复杂性的算法的NP问题。 这样，人们相信PNP是有原因的，因为在研究NP问题的过程中，发现了一个非常特殊的NP问题，称为NP-完全问题，也就是所谓的NPC问题。
2.NP-完全问题(NPC问题)一个问题约定为另一个问题，增加了时间复杂度，也增加了问题的适用范围。 约定某个问题可以继续寻找应用范围更广的算法，而不是复杂度更高、复杂度低但只能用于小类型问题的算法。
如果从一个NP问题不断升级，不断发现一些小的NP问题“能整个吃掉”稍微复杂一点的大的NP问题，最后找到时间上最复杂、且所有的NP问题都“能整个吃掉”的超级NP问题
NP类问题：存在这样的NP问题，所有NP问题都与之近似。 这样的问题不止一个，还有很多，那是一种问题。 这样的问题是NPC问题。
NPC问题：同时满足以下两个条件的问题就是NPC问题。 首先，必须是NP问题。 而且，所有的NP问题都可以概括为它。
http://www.Sina.com/NPC问题至少证明是一个NP问题，然后证明已知的NPC问题之一可以约化。 (根据约定化的传达性，也满足NPC问题定义的第二条)
NPC问题的定义：
问题a可以近似为问题b :可以用解决问题b的方法解决问题a； 或者，问题a可以转换为问题b。 (例如，如果二次项系数a=0，则一元二次方程的解法可以用于求解一元一次方程) ) )。
问题a可以近似为问题b的时间复杂度高于或等于a的时间复杂度的直观意义。 也就是说，问题a不比问题b难。
约定事项具有传达性：如果问题a可以约定为问题b，问题b可以约定为问题c，则问题a一定可以约定为问题c。
约定事项的标准概念：如果任何一个程序a的输入，按照其规律转换为程序b的输入，发现两个程序的输出相同的变化规律，那么问题a就可以约定为问题b。
3.NPC硬件问题NP -硬件问题符合NPC问题定义的第二条，不符合第一条。 NP-hard问题的范围比NP问题更广。
NP-hard问题也很难找到多项式时间复杂度的算法，但它不一定是NP问题(只是所有NP问题都可以与之近似)。
NPC问题的证明：:指问题s，满足任何NP问题都可以多项式级时间复杂度归结为s (归纳性：即归纳性NP问题与s的答案相同，解s同时求解所有NP问题)。 可以理解为这是比所有NP问题更难的问题。
补充约化的概念
2000年，美国克雷数学研究所发表了世界七大数学课题，也被称为千年大奖的课题。 其中，PP和NP问题被列为这七大世界难题之首，从而大大激发了人们对这一问题的研究热情。
普林斯顿大学计算机系大楼表达二进制代码的“P=NP？ ”问题刻在顶层西边的砖头上。 如果P=NP得到证明，砖头就会显示“P=NP！ ”可以简单地说。
康奈尔大学的Hubert Chen博士提供了这个笑话p不等于NP的证明：
反证法。 设定P=NP。 将y作为一个P=NP的证明。 证明y可以用合格的计算机科学家在多项式时间内验证，并将这类科学家的存在性认定为真。 但是，由于P=NP，这个证明y可以在多项式时间内由这样的科学家发现。 但是，这样的发现还没有发生，这样的科学家试图发现这样的证明，但我们得到了矛盾。 (以上内容来自维基百科)
NP-hard问题
店员旅游问题(traveling salesman problem )是最具代表性的NP问题之一。 假设一个推销员需要从香港出发，经过广州、北京、上海、……等n个城市，最后返回香港。 每个城市之间都有飞机直达，但票价不同。 如果现在公司只报销c美元，你问他有没有时间表让他穿越所有城市，总旅费比c小吗？
推销员旅行问题显然是NP的。 因为只要出示任意的日程，就可以很容易地算出旅行的总支出。 但是，为了知道是否存在总旅费不足c的旅行，最坏的情况是必须检查所有可能的旅行日程！ 这将是天文数字。
这是
个天文数字到底有多大？目前的方法接近一个一个的排着试，还没有找到更好可以寻得最短路径的方法。对七个城而言，共有 6!=720 个排法，还比较简单；，但若有 20 个城，则排法就有 19! 种。因故在排列组合里 n! 写起来轻松。但 1.21∗10171.21∗1017 是一个大得不得了的数字。若每秒钟排一次，要排 3.84∗1093.84∗109 年（一年约为 3.15∗1073.15∗107 秒），即使使用计算器，每秒排一百万次（不容易做到）也得重做三千年才能找到答案。「生也有涯，知也无涯」，想不到区区二十个城，要三十个世纪才能找到答案。4.组合最优化问题
组合最优化问题（combinatorial optimizationproblem）是一类在离散状态下求极值的问题。把某种离散对象按某个确定的约束条件进行安排，当已知合乎这种约束条件的特定安排存在时，寻求这种特定安排在某个优化准则下的极大解或极小解的间题。
组合最优化的理论基础含线性规划、非线性规划、整数规划、动态规划、拟阵论和网络分析等。组合最优化技术提供了一个快速寻求极大解或极小解的方法。
多数问题属于所谓的NP完全问题，即对该问题基本上不存在一种算法，使得当所有的具体问题的变量和约束条件的数目两者之和甚大时，可以在容许时间（即所谓的多项式时间）之内给出所要的解。
由于这类问题在生产实际中经常出现，不能予以忽视，于是出现了两类解决问题的途径：一类是所谓的直观算法，另一类是近似算法。随着组合最优化研究的进展，一些数学分支，如组合数学、拟阵和广义拟阵以及图论等，也相应地得到新的发展。