算法概论:多项式归约、P、NP、NP完全问题

归约

设计一个函数f(x),把问题A的输入转换成问题B的一个输入,这样就能用问题B的解法来求解。(输出真或假)
转换函数f(x)的设计必须要保证问题B的输出结果和相应的问题A上的答案保持一致。
这样就是一个归约技术,将这个问题转换为类似的其他问题。

多项式归约

归约是指A的输入x经过f(x)转换成B的输入x’,所谓多项式归约是指转换函数f(x)不能太复杂,需要在多项式时间内完成。如果是指数级或其他复杂度就没有意义了。
符号是一个小于等于号加上下标一个p代表多项式。
A多项式归约B,意味着问题B至少和求解问题A一样难,意义跟小于等于号类似。
多项式归约实际是用来比较解决两个问题的难度大小关系。

多项式归约的性质

建立多项式可解性
B多项式可解则A也多项式可解。
建立建立难解关系(intractability)
A多项式不可解则B也多项式不可解。
建立等价性
A、B相互归约,则 A B两个问题等价。

多项式归约的方法

具体如何做多项式归约呢?

  • 通过简单等价性
  • 通过一般情况归约
  • 通过编码

简单等价性

这里举一个例子,一个问题是独立集问题,一个问题是顶点覆盖问题。
独立集:求一个子集S,顶点数>=k,其各顶点之间相互独立,没有边相连。
(假装有图)
k=6: 存在
k=7:不存在

顶点覆盖:求一个子集S,顶点数<=k,
(假装有图,跟上一张图一样)
k=4:存在
k=3:不存在

两个问题是一个等价问题,解是互补关系。
证明略。

一般情况归约

这里同样举两个例子。
集合覆盖(set cover)
设有一个所有元素的集合U,U有S1,S2,S3...Sm的元素子集,是否存在<=k个子集的集合,他们的并集就是U。

顶点覆盖问题
如上。

这两个问题之间可以相互归约,顶点覆盖问题可以看做集合覆盖问题的特殊情况。
即:U是所有边的集合,每个子集相当于一个顶点,子集内是该顶点关联的边。

编码

问题A和问题B的形式上差距很大,需要通过零件编码(encode with gadgets)?
同样举两个例子。

布尔公式可满足问题
布尔变量的析取构成子句,子句的合取构成公式。
问题是:是否存在一组布尔变量满足公式为真。
这个问题非常复杂,所以有一个简化的问题:每个子句含有三个布尔变量,求公式的可满足解。 这就是3-SAT可满足问题。

独立集问题
如上。

两个问题看起来差距很大(不是看起来好吧),但其实也是可以相互归约的。
将3-SAT问题归约成一个图的独立集问题
具体怎么编码呢?通过布尔公式构造一个图,图怎么构造呢?公式是由多个子句构成,每个子句构成一个子图,所以每个子图是一个三角形,有三个顶点对应三个布尔变量。将每个变量和它的否定之间加一条边,这样就把边加上去了。
(假装有图)
寻找可满足解实际就是独立集问题,独立集问题中的k取公式中子句的数量,通过这样一个构造方式,3-SAT问题就被归约成了一个图的独立集问题。
我们需要证明这个归约过程是有效的:证明:S如果是图里的一个独立集<--->可以找到一个可满足解

证明
S如果是一个独立集,那么S在这个图里,每个三角形里最多包含一个顶点,否则不是独立集。将所有这些点设置为true,则这个公式一定可以满足。
反过来,如果是一个可满足解,在每个子句里,选择一个为true的文字量,将三角形里对应的点选出来,这些点union起来就是一个独立集。

有了这个归约技术以后,则可以进行问题之间难度的比较关系。归约满足传递性。

NP完全性

有了多项式归约这个基础,就可以解释NP完全性。之前讨论算法时,经常会讨论到可以把一个很复杂的问题用一个巧妙的多项式方法解决。实际上,有很多实际的问题,以目前的技术是很难给出有效的多项式解法,这些问题就是NP完全问题,代表困难问题。比如0-1背包问题等。
特别关心哪些问题是属于NP完全问题,要了解问题的难度,可以设计启发式的算法、近似解、使用指数级复杂度算法。。

接下来讨论三类问题
P类问题,NP问题,NP完全问题。
Class P P类问题是代表一类问题,这个P代表Polynomia多项式,所有多项式时间内可解的问题都属于P类问题。比如常数时间,分治法中的求中位数等。
不属于P类问题的问题有intractable和unsolvable,比较经典的不可解问题是图灵停机问题,halting problem,给你任意一个算法和它的输入,设计一个算法判断它是否是无限循环,能否终止。
有些问题属于难处理问题,难到什么程度呢?一个叫NP完全问题 一个叫NP困难问题。
N:Nondeterministic,非确定性,算法的执行过程是不确定的。如果一个算法由两个步骤构成的,生成一个随机解certificate,猜出一个随机解,第二步进行验证猜的解对不对。这样一个算法称为非确定性算法,第一个阶段是不确定的,第二个阶段是确定的。
P:polynomia,验证阶段是多项式的。
P和NP是否相等?is P = NP ?
any problem in P is also in NP
NP属于P还没有证明。

NP完全问题,NP问题里最难的问题,大多数实际问题要么是P问题要么是NP完全问题,但P和NP都只是所有实际问题的子集。
B是NP完全问题,(1)B是NP问题,(2)所有属于NP问题的A 都可以归约成问题B。
如果B只满足(2),则B是NP-hard问题。

目前没有人证明NP是不能多项式可解,也没人证明NP是多项式可解。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,784评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,745评论 2 378
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,702评论 0 335
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,229评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,245评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,376评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,798评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,471评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,655评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,485评论 2 318
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,535评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,235评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,793评论 3 304
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,863评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,096评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,654评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,233评论 2 341

推荐阅读更多精彩内容