NP问题

NP问题

一个NP－完全的问题具有如下性质：它可以在多项式时间内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP问题是所有可用多项式时间算法验证其猜测准确性的问题的集合。

令L1和L2是两个问题，如果有一确定的多项式时间算法求解L1，而这个算法使用了一个在多项式时间内求解L2的确定算法，则称L1约化为L2。如果可满足性约化为一个问题L，则称L 问题是NP-难度的。如果L是NP难度的且L（－NP，则称L是NP－完全的。NP并不是NON-POLYNOMIAL，把NP说成是N ON-POLYNOMIAL，是望文生义，读书不求甚解。事实上，如果你能够证明某个NP问题是个NON-POLYNOMIAL的问题，你就可以去领那七个百万美元数学大奖中间的一个了。数学上著名的NP问题，完整的叫法是NP完全问题，也即“NP COMPLETE”问题，简单的写法，是NP=P？的问题。问题就在这个问号上，到底是NP等于P，还是NP不等於P。证明其中之一，便可以拿百万美元大奖。这个奖还没有人拿到，也就是说，NP问题到底是Polynomial，还是Non-Polynomial，尚无定论。Mr. X信口开河敢说NP就是Non-Polynomial，真是不知天高地厚，惹人笑话。NP里面的N，不是Non-Polynomial的N，是Non-Deterministi

c，P代表Polynomial倒是对的。NP就是Non-deterministic Po lynomial的问题，也即是多项式复杂程度的非确定性问题。

什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。

人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能

答案，都可以在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。

有些看来好像是非多项式的问题，其实是多项式问题，只是人们一时还不知道它的多项式解而已。

P = NP?

这个问题，作为理论计算机科学的核心问题，其声名早已经超越了这个领域。它是Clay研究所的七个百万美元大奖问题之一，在2006国际数学家大会上，它是某个1小时讲座的主题。

要说起P和NP是什么东西，得先从算法的多项式时间复杂度谈起，注意，这里面的两个P都是指Polynomial。

一个问题的规模指的是输入的总位数，比如一个n个数的排序问题，输入规模就是n。注意，在某些时候，输入规模是要值得注意的，比

如判定一个数n是否是一个质数这个问题，它的输入规模并不是n，而是log(n)，因为一个数n用大约log(n)位就能表示出来了，这也是为何枚举因子判定素数的算法并不是多项式时间算法的原因。

如果一个算法，它能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多项式时间算法。注意：这里的多项式时间是指算法运行的步数。一个算法是否是多项式算法，与计算模型的具体的物理实现没有关系，虽然大多数假想的计算模型不可能有任何物理的实现。

P指确定型图灵机上的具有多项式算法的问题集合，NP指非确定型图灵机上具有多项式算法的问题集合，这里N是Non-Deterministic的意思（图灵机的概念见理论计算机初步：算法和计算模型）。

脱离图灵机的概念，就在普通的计算机上看，P问题是指能够在多项式时间求解的判定问题（判定问题指只需要回答是和不是的问题），而NP问题则是指那些其肯定解能够在给定正确信息下在多项式时间内验证的判定问题。比如，要判定一个数是合数，如果给我一个约数，我们就很快判定它就是合数。所以判定一个数是合数的问题属于NP。下面是一些NP问题的例子：

零子集和问题

给n个整数，判断是否可以从中找到若干个数，其和为0。

旅行商问题

有n个城市，一个推销员要从其中某一个城市出发，不重复地走遍所有的城市，再回到他出发的城市。问这个推销员的最短路程(是否小于指定的K)。

从上面的定义知道，NP包含P。P vs NP问题指P是否完全等于NP，即确定型图灵机和非确定图灵机的性能是否一样。

人们为何要提出NP问题？因为，大多数遇到的自然的难解问题，最后都发现它们是NP问题。如果我们能证明NP跟P的关系，则解决了无数问题的算法复杂度问题。

NP里面有无数个不同的问题，我们是否要一个一个地判定它们是否属于P呢？P vs NP问题的美妙和简洁之处便在于在NP中，有一个子类，NP完全(NP Complete，简记为NPC)问题，指的是那些NP中最难的那些问题：所有其它的NP问题都可以归约到这些NP完全问题。也就是说，只要这些NP完全问题的某一个得到解决，无论是证明其存在多项式算法，还是不存在，都意味着P vs NP问题的解决。

而几乎所有NP里面无法确定是否属于P的问题最后都被证明为NP完全。正因为如此，多数理论计算机学家都猜测P≠NP。目前已知的NP 完全问题数以千计，上面引用中的例子都是完全问题，更多NP完全问题见NP完全问题的不完全列表。

一个很自然的想法是如果NP≠P，则NP-P里面的问题都是完全问题。至少有两个自然的问题，一个是大数分解（给出一个数的质因数分解

式），另一个是图同构问题（给出两个图，它们是否同构），它们既没有被证明是P的，也没有被证明是NP-完全。但是更惊人的是还有这个定理：

如果NP≠P，那么NP-P中存在非NP完全问题。

当然，这种问题具体是什么样子，是无法用直观的语言表示出来，它纯粹是一个数学上的构造性证明。

清华大学算法分析与设计课件第10讲_NP完全性理论

Lecture 10. NP完全性理论 清华大学软件学院 清华大学 1 内容提要 ?计算模型与计算复杂度关系 ?问题分类：【P】与【NP】类 ?NP－难【hard】问题，NP完全集 ?第一个NPC问题和NPC问题集 ?如何证明一个问题是NPC问题

涉及到的算法理论基础 ?原则上是否存在一般数学问题的解题步骤的判决问题【希尔波特第十问题】 ?图灵机的停机问题：是否存在一个图灵机，他可以回答其它图灵机是否停机【既算法是有界的】 ?图灵公理：凡是可计算的函数都可以用一台图灵机来计算 ?P－NP－NPC问题定义及其猜想：NPC是一类不可以在多项式时间内计算的问题。 清华大学 3 明代数学家程大位著《算法统宗》中关于珠算的插图

机械式手动计算机 清华大学 5 机械计算机 ?法国数学家、哲学家帕斯卡在1642年发明了一种机械计算机，并与1649年取得专利。帕斯卡的计算机采用一种齿轮系统，其中一小轮转十个数字，下一个小轮便转动一个数字，通过齿轮系的联动，可以进行加法和减法的运算.

图灵 ?大半个世纪以来，数学家、计算机 科学家提出了各种各样的计算模型 都被证明是同图灵机器等价的。这 一理论已被当成公理，它不仅是计 算机科学的基础，也是数学的基础 之一。为纪念英国数学家Turing (1912-1954) 而设立的图灵奖成为计 算机界的诺贝尔奖. 清华大学7 图灵机模型

图灵机定义 ?一个图灵机是一个7元组(Q,∑,Γ,δ,q0,q1,q2), 其中Q,∑,Γ都是有穷集合,并且 ?1) ?2) ?3) 集. ?4) ?5) ?6) ?7) Q 是状态集. ∑是输入字母表,不包括特殊空白符号︺. Γ是带字母表,其中: ︺∈Γ,∑是Γ的子δ: Q×Γ→Q×Γ×{L,R}是转移函数. q0∈Q是起始状态. q1∈Q是接受状态. q2∈Q是拒绝状态,且q2≠q1 图灵机模型 ?图灵机模型用一个无限长的带子作为无限存储, 它还有一个读写头,这个读写头能在带子上读, 写和移动: 开始时,带子上只有输入串,其它地方都是空的.当它需要保存信息时,读写头就把信息写在带子上.为了读某个输入或写下的信息,带子可能将读写头往回移动到这个信息所 在的地方.这样读,写和移动,机器不停的计算, 直到产生输出为止.机器实现设置了两种状态: 接受或拒绝 清华大学9

控制图基础知识介绍

控制图基础知识介绍 一． 前言: 为使现场的质量状况达成目标，均须加以管理。我们所说的 “管理”作业,一般均用侦测产品的质量特性来判断 “管理”作业是否正常。而质量特性会随着时间产生显著高低的变化;那么到底高到何种程度或低至何种状态才算我们所说的异常?故设定一合理的高低界限,作为我们分析现场制程状况是否在 “管理”状态,即为控制图的基本根源。 控制图是于1924年由美国品管大师修哈特(W.A.Shewhart)博士所发明。而主要定义即是[一种以实际产品质量特性与依过去经验所研判的过程能力的控制界限比较,而以时间顺序表示出来的图形]。 二．控制图的基本特性: 一般控制图纵轴均设定为产品的质量特性,而以过程变化的数据为刻度;横轴则为检测产品的群体代码或编号或年月日等,以时间别或制造先后别,依顺序点绘在图上。 在管制图上有三条笔直的横线,中间的一条为中心线(Central Line,CL),一般用蓝色的实线绘制；在上方的一条称为控制上限(Upper Control Limit,UCL)；在下方的称为控制下限(Lower Control Limit,LCL)。对上、下控制界限的绘制,则一般均用红色的虚线表现,以表示可接受的变异范围;至于实际产品质量特性的点连线条则大都用黑色实线绘制。 控制状态: 三．控制图的原理: 1.质量变异的形成原因: 一般在制造的过程中,无论是多么精密的设备、环境,它的质量特性一定都会有变动,绝对无法做出完全一样的产品;而引起变动的原因可分为两种：一种为偶然(机遇)原因；一种为异常(非机遇)原因。 （1）偶然(机遇)原因(Chance causes)： 不可避免的原因、非人为的原因、共同性原因、一般性原因,是属于控制状态的变异。 （2）异常(非机遇)原因(Assignable causes): 可避免的原因、人为的原因、特殊性原因、局部性原因等,不可让其存 上控制界限(UCL) 中心线(CL) 下控制界限(LCL)

P 控制图

P 控制图的概述 可使用 P 控制图监视缺陷品比率（每个产品项都划分为两个类别中的一类，例如成功或失败）。使用此控制图可以监视过程在一段时间内的稳定性，以便您可以标识和更正过程中的不稳定性。 例如，送货服务经理可以使用P 控制图来监视 2 个月来送货车每天不工作的比率。不工作的送货车将被视为缺陷品。 此控制图表显示，在任何特定的一天中平均有8％的送货车不工作。第19 天的缺陷单元率不受控制。经理应确定导致缺陷品率异常高的任何特殊原因。 在何处查找此控制图 要创建P 控制图，请选择统计 > 控制图 > 属性控制图 > P。 什么情况下使用备择控制图 ?如果可以统计每项的缺陷数，请使用U 控制图、Laney U' 控制图或C 控制图来绘制单位缺陷数。 ?如果您的数据存在过度离散或欠离散现象，则Laney P' 控制图可更加准确地区分常见原因变异和特殊原因变异。过度离散可能导致传统P 控制图显示数量增加的超出控制限的点。欠离散可能导致传统P 控制图显示过少超出控制限的点。Laney P' 控制图可调整这些条件。您可以使用P 控制图诊断检验数据是否存在过度离散和欠离散现象。有关更多信息，请转到过度离散和欠离散。 注意

NP 控制图也绘制缺陷品。但是，P 控制图绘制缺陷品的比率，而NP 控制图绘制缺陷品的数量。 P 控制图的数据注意事项 为了确保结果有效，请在收集数据、执行分析和解释结果时考虑以下准则。 项必须分为两个类别之一（如通过或失败） 缺陷品有一个或多个使其不可接受的缺陷。如果您只能确定某项是否为缺陷品，请使用此控制图。如果可以统计每项的缺陷数，请使用U 控制图、Laney U' 控制图或C 控制图来绘制单位缺陷数。 如果您的数据存在过度离散或欠离散现象，则传统的属性控制图可能会产生误解如果您的数据存在过度离散或欠离散现象，则Laney P' 控制图可更加准确地区分常见原因变异和特殊原因变异。过度离散可能导致传统P 控制图显示数量增加的超出控制限的点。欠离散可能导致传统P 控制图显示过少超出控制限的点。Laney P' 控制图可调整这些条件。您可以使用P 控制图诊断检验数据是否存在过度离散和欠离散现象。有关更多信息，请转到过度离散和欠离散。 数据应当采用时间顺序 由于控制图会检测随时间发生的变化，因此数据顺序非常重要。您应当按照数据的收集顺序来输入数据，让最旧的数据位于工作表的顶部。 应当按照适当的时间间隔收集数据 按照均匀的时间间隔收集数据，如每小时一次、每班次一次或每天一次。选择一个时间间隔，该时间间隔应当足够短，以便您可以在发生过程更改之后立即识别此更改。 采用子组形式收集数据 子组是您要评估的过程中相似项的样本。应在相同的过程条件（如人员、设备、供应商或环境）下收集各子组的项。 如果子组是多个单位的集合，则应在相同的过程条件（如人员、设备、供应商或环境）下收集子组。如果不收集子组（即，其中的项具有相同的过程条件）数据，则可能无法区分常见原因变异和特殊原因变异。 子组必须足够大 如果子组不够大，则根据数据估计的控制限可能不准确。所需的子组大小() 取决于缺陷品的平均比率()。使用以下公式可以确定子组是否足够大：。例如，如果缺陷品的平均比率为0.06，则所有子组中都必须至少有9 项： ，舍入为最接近的整数9。 数据必须包括足够多的子组才能获取精确的控制限

质量管理控制图

质量管理 控制图实验

一、紫铜管的Xbar-R 控制图 C1, ..., C5 的 Xbar-R 控制图 C1, ..., C5 的 Xbar 控制图检验结果 检验 1。1 个点，距离中心线超过 3.00 个标准差。 检验出下列点不合格: 3 检验 6。5 点中有 4 点，距离中心线超过 1 个标准差（在中心线的同一侧） 检验出下列点不合格: 11 * 警告 * 如果使用新数据更新图形，以上结果可能不再正确。 二、某产品验收的交验批批量不等，试用不合格品率控制图样本号

样本号 样本容量(n) 不合格品数(d) 样本号 样本容量(n) 不合格品数 (d) 1 835 8 14 250 8 2 808 12 15 830 14 3 780 6 16 798 7 4 252 6 17 813 9 5 430 7 18 818 7 6 600 5 19 581 8 7 822 11 20 464 4 8 814 8 21 807 11 9 206 6 22 595 7 10 703 8 23 500 12 11 850 1 9 24 760 7 12 709 11 25 420 8 13 350 5 合计 15795 214

三、某厂生产一种零件，规定每天抽100件为一个样本，试用np 控制图对其质 量进行控制。 样本号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 不合格 品数di 3 4 0 4 3 3 2 2 2 5 4 1 1 2 0 3 0 6 0 4 4 1 0 6 4 样本容量均为ni =100；样本组数k =25；不合格品总数

第1章 算法概论(4np完全性理论)

1 §1.3 NP 完全性理论

如何理解问题的难解？易解？多项式运行时间？ ?多项式的运行时间认为是易解算法，当然，你认为θ(n100)难解，但次数如此高的多项式时间问题非常少，且一般都会找到一个更有效的多项式时间算法。 ?对很多合理计算模型来说，在一个模型上用多项式时间可解的问题，在另一个模型上也可以用多项式时间获得解决。 2

如何理解问题的难解？易解？多项式运行时间？ 多项式时间可解问题类具有很好的封闭性。比如一个多项式时间算法输出给另一个多项式时间算法作为输入，或被另一个多项式时间算法作为子程序常数次调用，这样的组合算法运行时间也都是多项式的。 3

?一般来说，将可由多项式时间算法求解的问题看成易处理的问题，而把需要超多项式时间才能解决的问题看作难处理问题。 ?“NP完全”（NP-Complete）问题，它的状态是未知的，迄今为止，既没有人找出求解NP完全问题的多项式算法，也没人能够证明对这类问题不存在多项式时间算法。 ?P≠NP问题，自1971年提出以后，已经成为理论计算机科学研究领域中，最深奥和最错综复杂的开放问题之一了。 4

5 ? 从表面上看，有些NP 完全问题有着与多项式时间算法的问题非常相似的特点，这很诱惑。? 最短与最长简单路径：有向图G=(V,E)，单源最短路径可在O(|V|2)时间内完成，但寻找两个顶点间最长简单路径（无重复顶点）问题是NP 完全的。?欧拉游程和哈密顿回路：有向图G=(V,E)，欧拉游程指一个回路，遍历途中每条边一次，但可能不止一次的访问同一个顶点，这可在O(|E|)时间内找到。哈密顿回路也是一个回路，包含V 中每个顶点。确定有向图是否存在哈密顿回路的问题是NP 完全的。

不合格品控制图P图 np图

P图 不良品率控制图(P图)是属于计数型控制图中的一种,是对产品不良品率进行监控时用的控制图 P图是用来测量在一批检验项目中不合格品（缺陷）项目的百分数。P图适用于全检零件或每个时期的检验样本含量不同 不良品率控制图(P图)的使用条件 不良品率控制图虽然是用来管制产品之不合格率，但并非适用于所有之不合格率数据。在使用不良品率控制图时，要满足下列条件: 1. 发生一件不合格品之机率为固定。 2. 前、后产品为独立。如果一件产品为不合格品之机率，是根据前面产品是否为不合格品 来决定，则不适合使用P图。 3. 如果不合格品有群聚现象时，也不适用P图。此问题通常是发生在产品是以组或群之 方式制造。例如在制造橡胶产品之化学制程中，如果烤箱之温度设定不正确，则当时所生产之整批产品将具有相当高之不合格率。如果一产品被发现为不合格，则同批之其他产品也将为不合格 不良品率控制图的操作步骤 1. 检验并记录数据 2. 计算平均不合格品率P 3. 计算中心线和控制界限（USL；LSL） 4. 绘制控制图并进行分析 举例说明： 【例】某除草机制造商以P控制图管制除草机在发动时是否正常。该公司每天抽取40部做试验，第一个月之数据如下表所示，试建立试用控制界限。

公司内部为PPM管理即百分比的不良率乘以1000000 使用EXCEL实现的方法 UCL= P+3*SQRT(P(1000000-P)/SQRT(n) LCL= P-3*SQRT(P(1000000-P)/SQRT(n)

不合格品数控制图 np控制图用于监测工艺过程中的不合格品数的变化是否处于可控状态，一般用于每批样本数n固定不变的情况。由于受监测的不合格品数等于每批样本大小n与不合格品率p的乘积np，因此不合格品数控制制图也叫做np控制图。 确定不合格品数控制图的控制限采用3σ方法，不合格品数随机变量D的均值μD=np，标准偏差，因此不合格品数控制图 （np图）的中心线和上下限控制限为：

控制图定义

控制图 control chart 根据假设检验的原理构造一种图，用于监测生产过程是否处于控制状态。它是统计质量管理的一种重要手段和工具。在生产过程中，产品质量由于受随机因素和系统因素的影响而产生变差；前者由大量微小的偶然因素叠加而成，后者则是由可辨识的、作用明显的原因所引起，经采取适当措施可以发现和排除。当一生产过程仅受随机因素的影响，从而产品的质量特征的平均值和变差都基本保持稳定时,称之为处于控制状态。此时,产品的质量特征是服从确定概率分布的随机变量，它的分布(或其中的未知参数)可依据较长时期在稳定状态下取得的观测数据用统计方法进行估计。分布确定以后，质量特征的数学模型随之确定。为检验其后的生产过程是否也处于控制状态，就需要检验上述质量特征是否符合这种数学模型。为此，每隔一定时间，在生产线上抽取一个大小固定的样本，计算其质量特征，若其数值符合这种数学模型，就认为生产过程正常，否则，就认为生产中出现某种系统性变化，或者说过程失去控制。这时，就需要考虑采取包括停产检查在内的各种措施，以期查明原因并将其排除，以恢复正常生产，不使失控状态延续而发展下去。 通常应用最广的控制图是W.A.休哈特在1925年提出的，一般称之为休哈特控制图。它的基本结构是在直角坐标系中画三条平行于横轴的直线，中间一条实线为中线(Cl)，上、下两条虚线分别为上、下控制界限（UCl和lCl）。横轴表示按一定时间间隔抽取样本的次序,纵轴表示根据样本计算的、表达某种质量特征的统计量的数值，由相继取得的样本算出的结果，在图上标为一连串的点子，它们可以用线段连接起来根据所考察的质量特征的性质是计量的还是计数的（包括计件和计点的）（见抽样检验），以及所采用的统计量的不同，控制图有不同的类型，常用的有以下几类：①适用于遵循正态分布的计量特征的平均数塣控制图和极差R控制图,这两个图必 须合用,一般称之为塣-R控制图。其中塣若用中位数塣代替,即成为塣-R控制图。 ②适用于遵循二项分布的计件特征的不合格品率p 控制图和不合格品数np控制图。 ③适用于遵循泊松分布的计点特征的缺陷数（或每单位缺陷数）с控制图。 以塣－R控制图为例来说明休哈特控制图的构造原理和使用方法。设所考察的产品的质量特征，在生产过程处于控制状态时，服从正态分布N(μ,σ2)，则样本大小为n的样本平均数塣服从N(μ,σ2/n)。因此对塣控制图，若以塣的数学期望μ为中线值，以为上、下控制界限,则适当选择k值，可以保证当过程处于控制状态时，样本平均数塣以很高的概率位于上下控制界限之间，而且应呈随机排列。例如当k=3时,此概率为99.7％。如果某个样本点落到控制界限之外，就认为生产过程失去控制；这种情况虽然在生产过程处于控制状态时也有可能发生,但其概率只有0.3％,可能性很小。在控制图中,一般取k=3,并称所得出的上、下控制界限是按3σ原则取的。虽然落在这些界限中的概率都很大，但并不都是99.7％。采用假设检验的想法，宁可冒微小的风险犯第一类错误而认为生产失控。还有一种可认为是失控的标志，是点子的排列呈现一种系统性的特征。比如有连续7个点子位于中线的一侧,或连续7点呈