NP的原理及定义和解释

NP 完全问题研究P=NP 的问题有两条基本思路：1．证明NP 类中的某些问题是难解的，从而得到NP ≠P 。

但是要证明这一点几乎同证明P=NP 一样困难。

2．考察NP 类中问题之间的关系，从中找到一些具有特殊性质的、与P 类问题显著不同的问题。

沿着这一路线人们已经证明了在NP 类中存在被称为NP 完全的子类，简称NPC 问题，并由此发展了一套著名的NP 完全理论。

本节简要先介绍NP 完全性理论。

为此，首先给出各语言之间的多项式变换的概念。

定义 1 所谓从一个语言*11∑⊆L 到另一个语言*22∑⊆L 的多项式变换是指满足下面两个条件的函数*2*1:∑→∑f ，(1) 存在计算f 的一个多项式时间DTM 程序；(2) 对于所有的*1∑∈x 有：1L x ∈当且仅当2)(L x f ∈。

用21L L ∝表示存在一个从语言1L 到语言2L 的多项式变换。

相应地，对于判定问题21,∏∏，设e 1和e 2是相应的编码策略。

若],[],[2211e L e L ∏∝∏，则记为21∏∝∏。

也可以从问题的层次来叙述：由判定问题1∏到判定问题2∏的多项式变换是满足下列条件的函数21:∏∏→D D f ，(1) f 可由一个多项式时间的确定性算法来计算；(2) 对于所有的1∏∈I D 有：1∏∈I D 当且仅当2)(∏∈I Y f 。

定义2 称一个语言L （判定问题∏）为NP 完全的（NPC ），如果)(NP NP L ∈∏∈，且对于所有别的语言NP L ∈'（判定问题NP ∈∏'）均有)'('∏∝∏∝L L 。

按照定义2，要证明问题∏是NP 完全的，需要证明所有的NP 问题均能够经多项式变换变成∏。

这几乎是很难做到的。

如果NP 完全问题比较多，我们也不能对每一个这样的问题都这样验证。

为此我们讨论一些NPC 问题的有用的性质。

性质1 如果L L ∝'，则P L ∈意味着P L ∈'。

【转】谈“P=NP？”“P=NP?” 通常被认为是计算机科学最重要的问题。

有⼀个叫的研究所，甚⾄悬赏 100 万美元给解决它的⼈。

可是我今天要告诉你的是，这个问题其实是不存在的，它根本不需要解决。

我并不是第⼀个这样认为的⼈。

在很早的时候就有个毫不客⽓的指出，P=NP? 是个愚蠢的问题，并且为了嘲笑它，专门在愚⼈节写了⼀篇“”，称⾃⼰证明了 P=NP。

我⾝边有⼀些⾮常聪明的⼈，他们基本也都不把这问题当回事。

如果我对他们讲这些东西，恐怕是 TOO OLD。

可是我发现国内的计算机专业学⽣，提到这个问题总是奉为神圣，⼀点玩笑也开不得，所以我打算在这⾥科普⼀下。

这是⼀个不⼤好解释的问题。

⾸先，你要搞清楚什么是“P=NP?” 为此，你必须先了解⼀下什么是“算法复杂度”。

为此，你⼜必须先了解什么是“算法”。

你可以简单的把“算法”想象成⼀台机器，就跟绞⾁机似的。

你给它⼀些“输⼊”，它就给你⼀些“输出”。

⽐如，绞⾁机的输⼊是⾁末，输出是⾁渣。

⽜的输⼊是草，输出是奶（或者⽜⽶⽥共）。

“加法器”的输⼊是两个整数，输出是这两个整数的和。

“算法理论”所讨论的问题，就是如何设计这些机器，让它们更加有效的⼯作。

就像是说如何培育出优质的奶⽜，吃进相同数量的草，更快的产出更多的奶。

通常所谓的“计算问题”，都需要算法经过⼀定时间的⼯作（也叫“计算”），才能得到结果。

计算所需要的时间，往往跟输⼊的⼤⼩有关系。

你的⽜吃的草越多，它就需要越长时间，才能把草都变成奶。

这种草和奶的转换速度，通常被叫做“算法复杂度”。

算法复杂度通常被表⽰为⼀个函数 f(n)，其中 n 是输⼊的⼤⼩。

这个函数的值，通常是某种资源的需求量，⽐如时间或者空间。

⽐如，如果你的算法时间复杂度为 n2，那么当输⼊10个东西的时候，它需要 100 个单元的时间才能完成计算。

当输⼊ 100 个东西的时候，它需要10000 个单元的时间才能完成。

当输⼊ 1000 个数据的时候，它需要 1000000 个单元的时间。

NP的原理及定义和解释NP是非确定性多项式（Non-deterministic Polynomial）的简称，是计算机科学中的一个复杂性类。

NP问题是指可以在多项式时间内验证解的正确性的问题。

NP问题的解可以通过非确定性多项式算法在多项式时间内验证，但没有有效的多项式算法可以在多项式时间内求解。

因此，NP问题的求解是非常困难的，往往需要使用暴力或近似算法等方法。

定义：NP问题的定义可以分为两个方面：1. 证书存在性：对于一个给定的问题，如果存在一个证书（certificate），可以在多项式时间内验证其正确性，则该问题属于NP 问题。

2.多项式时间验证：对于给定的问题和一个潜在的解，可以在多项式时间内验证这个解是否是正确的。

NP问题的解法可以由以下两种形式描述：1.非确定性算法：对于一个给定的问题，非确定性算法可以通过猜测和尝试的方式，在多项式时间内找到问题的解。

这个算法可以通过多次猜测和尝试来验证潜在的解是否是正确的，但并没有给出一个确定性的步骤来找到解。

2.多项式时间验证算法：对于一个给定的问题和一个潜在的解，可以通过一个多项式时间的验证算法，验证这个解是否是正确的。

原理：NP问题的原理基于两个关键概念：证书存在性和多项式时间验证。

证书存在性是指对于一个给定的问题，存在一个证书（或称为证明）可以在多项式时间内验证其正确性。

证书可以是一组状态、数字、字符串等，通过这个证书可以验证一个给定的解是否正确。

这个证书可以被看作是一个“快速验证器”，它能够在多项式时间内验证问题的解的正确性。

多项式时间验证是指对于给定的问题和一个潜在的解，可以在多项式时间内验证这个解是否是正确的。

多项式时间验证算法可以通过一系列的计算和判断，来验证一个给定的解是否满足问题的条件。

这个验证算法的运行时间是一个多项式，在实际应用中可以被认为是“快速”的。

基于以上两个概念，可以得到一个重要的结论：如果一个问题是NP 问题，那么可以把它的解转换成一个证书，并使用多项式时间验证算法，来验证这个证书的正确性。

你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。

你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。

他们没有搞清楚NP问题和NPC问题的概念。

NP问题并不是那种“只有搜才行”的问题，NPC问题才是。

好，行了，基本上这个误解已经被澄清了。

下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。

接下来你可以看到，把NP问题当成是NPC 问题是一个多大的错误。

还是先用几句话简单说明一下时间复杂度。

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。

也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。

不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如：找n个数中的最大值；而像冒泡排序插入排序等。

数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。

还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。

不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。

同样地，O(n^3+n^2)的复杂度也就是O(n^3)的复杂度。

因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。

我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。

P/NP问题P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”（Clay Mathematics Institute, 简称CMI）在千禧年大奖难题中收录。

P/NP问题中包含了复杂度类P与NP的关系。

1971年史提芬·古克(Stephen A. Cook) 和Leonid Levin 相对独立的提出了下面的问题,即是否两个复杂度类P和NP是恒等的（P=NP?）。

P和NP复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。

很可能，计算理论最大的未解决问题就是关于这两类的关系的:P和NP相等吗?在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。

[1] 对于正确的解答，有一个,000,000美元的奖励。

NP-完全问题(或者叫NPC)的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在NP中最不像在P中的。

(确切定义细节请参看NP-完全)理论计算机科学家现在相信P, NP,和NPC类之间的关系如图中所示，其中P和NPC类不交。

假设P ≠ NP的复杂度类的图解.如P = NP则三个类相同.本质上，P = NP问题问道：如果是/不是问题的正面答案可以很快验证，其答案是否也可以很快计算？这里有一个给你找点这个问题的感觉的例子。

给定一个大数Y,我们可以问Y是否是复合数。

例如，我们可能问53308290611是否有非平凡的因子。

回答是肯定的，虽然手工找出一个因子很麻烦。

从另一个方面讲，如果有人声称答案是"对，因为224737可以整除53308290611",则我们可以很快用一个除法来验证。

p问题和np问题
P/NP问题是在理论信息学中计算复杂度理论领域里没有解决的问题，它被“克雷数学研究所”在千禧年大奖难题中收录。

P/NP问题中包含了复杂度类P与NP的关系。

复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。

P问题就是能在多项式时间内解决的问题，NP问题就是能在多项式时间验证答案正确与否的问题。

用大白话讲大概就是这样。

所以P是否等于NP实质上就是在问，如果对于一个问题我能在多项式时间内验证其答案的正确性，那么我是否能在多项式时间内解决它？这个表述不太严谨，但通俗来讲就是如此。

谈⼀谈如何理解NP问题⼀概念引⼊1.1时间复杂度在计算机处理⼀个问题时，往往需要⼀定的时间，假设把这个问题复杂化（将这个问题进⾏扩展），那么把计算机处理这类问题的时间变化速率，称为解决这种问题所⽤算法的时间复杂度。

例如，⼀个枚举⼀定范围内的数字的问题，计算机所⽤时间会随着范围的变化⽽线性变化，由于是简单的枚举，所以时间复杂度可以记为O(n)，n可以代表这个范围⼤⼩。

在计算机处理问题时，由于算法设计不同，对应的时间复杂度也不⼀定相同。

1.2多项式级时间和⾮多项式级时间在众多的时间复杂度中，根据其表达式的特点，可以⼤致将它们划分为两个范畴，⼀个是多项式级⼀个是⾮多项式级。

它们各⾃表⽰什么意思呢？还记得⾼中数学中学习的函数吗，在学习不同函数时，最常做的⼀件事是观察它们的图像变化，可以发现，x作为底数的图像和x作为指数的图像在后期的变化简直有天壤之别。

这也正是需要将时间复杂度划分的原因（多项式级的时间复杂度在后期变化远⼩于⾮多项式级），将n作为底数的时间复杂度归为多项式级，n作为指数的归为⾮多项式级。

例如O(n)、O(log(n))、O(n^a)等就是多项式级的时间复杂度，像O(n!)和O(a^n)就是⾮多项式级的复杂度。

对于计算机来说需要处理的问题往往是很庞⼤的，如果采⽤⾮多项式级复杂度的算法，那么将浪费很⼤的资源。

1.3 P问题在解释了多项式级和⾮多项式级时间复杂度之后，P问题的概念就简单了。

对于众多的问题，通常把能够使⽤多项式级时间复杂度算法解决的问题称为P问题。

⼆什么叫NP问题2.1 约化⼀般，问题A可以约化为问题的B的解释是可以⽤解决问题B的⽅法解决问题A。

简单的说，也就是问题A是问题B的另⼀种形式，且问题A的复杂程度要⼩于等于问题B。

就像解⽅程组的问题，假如你会解⼆元⼀次⽅程组，那么你⼀定会解⼀元⼀次⽅程，在这个例⼦中，⼀元⼀次⽅程就是问题A，⼆元⼀次⽅程组就是问题B，问题A可以看作是问题B中另⼀个⾃变量系数为零的特殊“⼆元⼀次⽅程组”。