原文鏈接http://blog.csdn.net/Ying_Xu/article/details/51487977
————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
本周的內(nèi)容是NP問題欲主，NP的全稱是Non-deterministic Polynomial竞端，即多項式復(fù)雜程度的非確定性問題厕氨。百度上對NP的解釋是猪狈，P/NP問題是在理論信息學(xué)中計算復(fù)雜度理論里至今沒有解決的問題雕蔽。通俗的說猾漫，是將不可知的問題轉(zhuǎn)化為已知的問題闯团，進(jìn)而計算器復(fù)雜度函匕。
首先介紹多項式時間的規(guī)約，即Polynomial-Time Reductions耍目，通過解決另一個不同問題的假設(shè)的子程序，使用不包含子程序在內(nèi)的多項式時間來解決一個問題的方法徐绑。主觀上邪驮，一個多項式時間規(guī)約證明了第一個問題不比第二個問題難，因為只要對于第二個問題有有效的解決辦法傲茄，那么對于第一個問題就一定也存在解決方法毅访。
根據(jù)計算的復(fù)雜度，我們可以將問題分為兩類盘榨，一種是可以在多項式時間內(nèi)解決的喻粹，另一種是不能在多項式時間內(nèi)被解決的。下面的表格給出了一些算法草巡。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
一些問題被證明需要指數(shù)時間：
1.給定一臺圖靈機守呜，它能否在最多k步的時候停止？
2.給定一個nxn的棋盤山憨，黑棋能夠保證贏嗎查乒？
一個不樂觀的消息是幾十年來大量的基礎(chǔ)問題都忽略了分類。這一節(jié)的內(nèi)容是表明這些基本問題是計算等價的郁竟，似乎是一個非常難問題的不同表現(xiàn)玛迄。
假設(shè)我們可以在多項式時間內(nèi)解決X問題，那么我們在多項式時間內(nèi)能解決其他什么問題嗎?這里引入Reduction的定義棚亩。
Reduction：問題X可以多項式規(guī)約為問題Y蓖议，如果問題X的任意實例可以使用下面的條件被解決：
A） 多項式數(shù)量的標(biāo)準(zhǔn)計算步驟加上，
B） 可以解決問題Y的oracle多項式數(shù)目次的調(diào)用讥蟆，這里勒虾，oracle是特殊硬件提供的可以在單步中解決Y的實例的計算模型。
表示為
這里瘸彤，X是已知的可以在多項式時間內(nèi)解決的問題从撼，Y是不可知復(fù)雜度的問題。中間的符號表示，有方法將X轉(zhuǎn)換為Y低零，有點類似于小于等于符號的含義是表明X的復(fù)雜度小于等于Y的復(fù)雜度婆翔，一般情況下，符號中p的上面會有一個m掏婶，表示可以是many to one reduction,也就是可以是多對一的映射。如果X有polynomial-time解雄妥，那么該解是下界最蕾；如果Y有polynomial-time解，那么該解是上界老厌。
因此多項式時間的規(guī)約的目的是根據(jù)問題的相對困難度來對問題分類的瘟则。如果有
我們也可以建立等價性，這里的等價是指的reduction的成本薇溃。如果
下面有三個基本的規(guī)約策略沐序，通過簡單等價規(guī)約琉用、從特殊案例到一般案例的規(guī)約和通過子程序的編碼來規(guī)約。
一策幼、簡單等價規(guī)約
首先定義獨立集（IndependentSet, 我們在Matroid中已經(jīng)學(xué)習(xí)過）辕羽，給定一個圖G=(V, E)和一個整數(shù)k，存在一個頂點的子集
如下圖：
? ? ? ? ? ? ? ? ? ?
對于上圖到逊，存在一個大小大于等于6的獨立集铣口，但是不存在大小大于等于7的獨立集。
下面定義一個頂點覆蓋集觉壶，給定一個圖G=(V, E)和一個整數(shù)k脑题，存在一個頂點的子集
例如：
? ? ? ? ? ? ? ? ? ?
對于上圖，存在一個大小小于等于4的頂點覆蓋集，但是不存在一個大小小于等于3的頂點覆蓋集已艰。
對于頂點覆蓋集合和獨立集痊末，有
其實從上面兩個圖，我們就可以看出哩掺，兩個集合互補凿叠。S是一個獨立集當(dāng)且僅當(dāng)V-S是一個頂點覆蓋集。
? ? ? ? ? ? ? ? ? ?
從上面等價條件來嚼吞，我們可以從
令S為任意的獨立集，考慮一條任意的邊(u, v), 因為S為獨立集
因此舱禽，V-S包含(u, v).
令V-S為任意的頂點覆蓋集炒刁，考慮兩個頂點u∈S和v∈S，因為V-S是一個頂點覆蓋集誊稚，觀察到(u, v)?S翔始，因此，不存在S中的兩個頂點連接同一條邊片吊。因此，S是一個獨立集协屡。
二俏脊、從特殊案例到一般案例的規(guī)約
定義集合覆蓋：
集合覆蓋（Set Cover）：給定一個元素的集合U，一個U的子集的集合S1,S2,…Sm,和一個整數(shù)k肤晓，存在一個集合含有小于等于k個這樣的集合的并等于U爷贫。
例：
? ? ? ??
上面的例子中，S2和S6即為滿足的集合补憾。
頂點覆蓋集合(Vertex cover)可以規(guī)約為集合覆蓋（Set Cover）漫萄，即
證明：
給定一個頂點覆蓋集合的實例G=(V,E),k,我們建立了一個集合覆蓋實例，其大小等于頂點覆蓋實例的大小盈匾。
創(chuàng)建過程：
創(chuàng)建集合覆蓋實例：
集合覆蓋的大小小于等于k當(dāng)且僅當(dāng)頂點覆蓋的大小小于等于k腾务。
? ? ? ?
三、通過子程序的編碼來規(guī)約削饵。
首先定義
literal：一個布爾變量或者它的否定：
clause子句：literal的析妊沂荨：
合取范式（Conjunction Normal Form， CNF）：子句clause的聯(lián)合的一個命題公式
SAT：給出一個CNF公式
3-SAT：每一個子句包含恰好3個literals的SAT
? ? ??
上面的例子是一個SAT窿撬，但不是一個3-SAT启昧。第3個clause再加一個literal就為3-SAT。
3-SAT可以規(guī)約到獨立集劈伴，即
證明：
給定一個3-SAT的實例
創(chuàng)建過程：
G對于每一個子句包含3個頂點严里，對每一個literal有1個頂點新啼；一個三角形中一個子句中連接3個literals；每一個literal連接到自身的否定田炭。
? ? ? ? ? ??
3可滿足性可以規(guī)約到獨立集师抄。
G包含一個大小為
證明：
→
令S為大小為k的獨立集叨吮，那么S在每一個三角形中包含恰好一個頂點，將這些literal全部設(shè)置為true瞬矩，茶鉴，其余的變量也保持一致，那么真命題賦值是一致的且所有的子句都滿足
←
給定一個滿足的命題景用， 從每一個三角形中選擇一個為真的literal涵叮。那么這就是一個大小為k的獨立集。
總結(jié)一下以上三種基本的規(guī)約方法：
? ? ? ? ?
傳遞性：
? ? ? ? ? ??
如：
? ? ? ? ?
決策問題：是否存在一個大小小于等于k的頂點覆蓋?
搜索問題：找到有著最小基數(shù)的頂點覆蓋
自規(guī)約性：搜索問題決策問題伞插，將會應(yīng)用到這一章節(jié)的所有問題中割粮，并且
證明我們對于決策問題的聚焦。
例如：
我們想要找到具有最小基數(shù)的頂點覆蓋
方法為：
（二進(jìn)制）搜索找到最小頂點覆蓋的基數(shù)k*
找到一個頂點v使得G-{v}有一個大小小于等于k*-1的頂點覆蓋（在任何的最小頂點覆蓋中的任意頂點都有這個性質(zhì)）
將v包含到這個頂點覆蓋中
遞歸找到一個最小的頂點覆蓋G-{v}
下面開始探討重點的NP問題
首先是決策問題媚污。
X是字符串的一個集合舀瓢，有一個實例字符串s，那么設(shè)計一個算法A解決問題X：使得A(s)=yes當(dāng)且僅當(dāng)s∈X
如果算法A是對于每一個字符串s運行在一個多項式時間內(nèi)的耗美，那么A(s)將會在最多第p(|s|)步終止京髓，其中p(·)是某一個多項式。
定義P：
對一個有著多項式運行時間的算法的決策問題
? ? ? ? ? ?
NP問題：
認(rèn)證算法的意圖：
Certifier（證明者）是從管理的角度來看待事情的商架，并不能自己決定是否有s∈X堰怨，然而，他可以檢驗一個提出的證明這個s∈X蛇摸。
定義：算法C(s,t)是一個問題X的證明者备图，如果對于每一個字符串s有s∈X當(dāng)且僅當(dāng)存在一個字符串t使得C(s,t) = yes.
NP是指存在一個多項式Certifier的決策問題，這是相對于P而言的定義赶袄。
例子：
給出一個整數(shù)s诬烹，s是一個合數(shù)（質(zhì)數(shù)的對立）嗎驹吮？
Certificate ：s的一個非質(zhì)因子t慧邮，存在這樣的一個憑證存在當(dāng)且僅當(dāng)s是一個合數(shù)擅这。
Certifier:
? ? ? ? ? ??
如一個實例：
s = 437699
Certificate: t = 541 或者809
結(jié)論是：合數(shù)是一個NP問題
SAT：給出一個CNF公式
Certificate：對于n個布爾變量的真值的賦值
Certifier：檢查
例如：
實例s
Certificate：
結(jié)論：SAT是一個NP問題
哈密頓環(huán)（Hamiltonian Cycle）
哈密頓環(huán)是：給定一個無向圖G=(V, E), 存在一個簡單環(huán)C能夠訪問每一個結(jié)點
Certificate：n個結(jié)點的排列
Certifier：檢驗排列中V中包含的每一個結(jié)點是否恰好出現(xiàn)一次扳还，并且在排列中每一對相鄰的結(jié)點之間是否存在一條邊韭寸。
結(jié)論：哈密頓環(huán)是一個NP問題
? ? ? ??
?
那么P是否等于NP呢背零？
所有的完全多項式非確定性問題，都可以轉(zhuǎn)換為一類叫做滿足性問題的邏輯運算問題汰聋。既然這類問題的所有可能答案门粪，都可以在多項式時間內(nèi)計算，人們于是就猜想烹困，是否這類問題玄妈，存在一個確定性算法，可以在多項式時間內(nèi)髓梅，直接算出或是搜尋出正確的答案呢拟蜻？這就是著名的NP=P？的猜想枯饿。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
如果yes：那么有效的算法對3-Color酝锅，TSP， FACTOR奢方， SAT…
如果No：沒有有效的算法對3-Color搔扁，TSP， FACTOR蟋字， SAT…
一致的輿論為p≠NP
最后討論的是NP完全問題稿蹲。
問題X多項式規(guī)約（polynomial reduces, Cook提出的）到問題Y，如果問題X的任意實例可以使用下面的來解決：
A． 多項式數(shù)目的標(biāo)準(zhǔn)計算步驟鹊奖，加上
B． 可以解決問題Y的oracle的多項式數(shù)目的調(diào)用
多項式轉(zhuǎn)換(polynomialtransforms, Karp提出的)是指問題X多項式轉(zhuǎn)換為問題Y如果給定一個任意的輸入x給X苛聘，我們可以生成一個輸出y使得x是X的一個yes實例當(dāng)且僅當(dāng)y是Y的一個yes實例。
多項式轉(zhuǎn)換是一個對于Y而言只有一個oracle調(diào)用的多項式規(guī)約嫉入，就在對X的算法的最后焰盗。幾乎所有之前的規(guī)約都是這種形式璧尸。
那么這兩個對于NP而言是相同的嗎咒林？
NP完全問題是最難的問題。它的定義是：NP中的一個問題Y有這樣的一個性質(zhì)：對于NP中的任意問題X爷光，有
完全多項式非確定性問題可以用窮舉法得到答案，一個個檢驗下去徐裸，最終便能得到結(jié)果遣鼓。但是這樣算法的復(fù)雜程度，是指數(shù)關(guān)系重贺，因此計算的時間隨問題的復(fù)雜程度成指數(shù)的增長骑祟，很快便變得不可計算了回懦。
定理：假設(shè)y是一個NP完全問題，那么y可以在多項式時間內(nèi)解決當(dāng)且僅當(dāng)P=NP
證明：
←如果P=NP次企，那么因為y是一個NP問題怯晕，因此可以在多項式時間內(nèi)被解決
→假定y可以在多項式時間內(nèi)被解決，令X為任意一個NP問題缸棵。因為
下面描述一個電路可滿足性問題型诚，在理論計算機科學(xué)中客燕，電路可滿足性問題（CIRCUIT-SAT）是決定一個給定的布爾電路是否有一個可以使得輸出為true的輸入的賦值的決策性問題。
給出一個由AND狰贯，OR和NOT門的聯(lián)合電路也搓，是否存在一個方法設(shè)置電路的輸入使得其輸出為1？
? ? ? ? ? ? ? ? ? ?
我們可以驗證涵紊，CIRCUIT-SAT是一個NP完全問題傍妒。
證明：任何一個將固定數(shù)目的n位作為輸入并且產(chǎn)生一個yes/no的輸出的算法都可以被這樣的一個電路來表示。并且摸柄，如果該算法花費多項式時間颤练，那么電路也是多項式大小。（固定為n位是非常重要的驱负，反應(yīng)了算法和電路之間的基本區(qū)別）
考慮一個NP問題X嗦玖，它有一個多項式時間certifier C(s, t).為了決策s是否在X中，我們需要知道是否存在一個長度為p(|s|)的憑證t使得C(s, t)=yes跃脊。
我們將C(s, t)看做是一個|s|+p(|s|)位的算法（輸入為s宇挫，憑證為t），將其轉(zhuǎn)化為一個多項式時間的電路K酪术。前|s|位是用s硬編碼的器瘪，剩下的p(|s|)位是t的位，那么電路K是可滿足的當(dāng)且僅當(dāng)C(s,t)=yes绘雁。
例如：
? ? ? ? ? ? ??
上面的電路就創(chuàng)建了一個電路K橡疼，它的輸入這樣被設(shè)置使得K輸出為真當(dāng)且僅當(dāng)圖G有一個大小為2的獨立集。
那么如何建立一個NP完全問題呢庐舟？
一旦我們建立了第一個NP完全問題欣除，那么其他的也就是一個道理了。
建立問題y的完全NP問題的步驟：
1） 表明Y是一個NP問題
2） 選擇一個完全NP問題X
3） 證明
可以證明3-SAT是一個NP完全問題挪略。
下面這個圖顯示了NP完全問題以及可以多項式規(guī)約到另一個問題历帚。
? ? ? ? ? ? ??
NP完全問題的6個種類和典型例子：
a)??包裝問題：SET-PACKING废酷，INDEPENDENT SET
b)??覆蓋問題：SET-COVER， VERTEX-COVER
c)??約束滿足問題：SAT抹缕， 3-SAT
d)??序列問題：HAMILTONIAN-CYCLE澈蟆， TSP
e)??分區(qū)問題：3D-MATCHING, 3-COLOR
f)??數(shù)值問題：SUBSET-SUM， KNAPSACK
大部分的NP問題要么是P要么就是完全NP問題卓研。
NP的對稱：我們只需要有對于yes實例的簡單證明即可趴俘。
1.? SATvs. TAUTOLOGY
可以證明對于一個給定的賦值，一個CNF公式是可以滿足的奏赘，那么如何證明一個公式不可滿足呢寥闪？
2.? HAM-CYCLEvs. NO-HAM-CYCLE
給定一個哈密頓環(huán)可以證明一個圖是哈密頓，那么如何證明一個圖不是哈密頓呢磨淌？
??????? co-NP是NP決策問題的補集疲憋。
? ? ? ? ??
那么，NP=co-NP呢梁只？
一致的輿論是不等于的缚柳。
如果有NP≠co-NP，那么P≠NP搪锣。但可以得出秋忙，
質(zhì)數(shù)問題是一個NP∩co-NP的問題
（Pratt定理）一個奇數(shù)是一個質(zhì)數(shù)當(dāng)且僅當(dāng)存在一個整數(shù)1<t<s,使得對于所有s-1的所有素除子p有
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
??? FACTORIZE：給定一個整數(shù)x构舟，找出它的素因子
??? FACTOR：給定兩個整數(shù)x和y灰追，找出x是否有一個小于y的非質(zhì)因子。
??? 定理：
??? FACTOR是一個NP∩co-NP的問題狗超。
? ??
版權(quán)聲明：本文為博主原創(chuàng)文章弹澎，未經(jīng)博主允許不得轉(zhuǎn)載。
