歸約
設(shè)計(jì)一個函數(shù)f(x)暗甥，把問題A的輸入轉(zhuǎn)換成問題B的一個輸入喜滨，這樣就能用問題B的解法來求解。（輸出真或假）
轉(zhuǎn)換函數(shù)f(x)的設(shè)計(jì)必須要保證問題B的輸出結(jié)果和相應(yīng)的問題A上的答案保持一致撤防。
這樣就是一個歸約技術(shù)虽风，將這個問題轉(zhuǎn)換為類似的其他問題。
多項(xiàng)式歸約
歸約是指A的輸入x經(jīng)過f(x)轉(zhuǎn)換成B的輸入x’寄月，所謂多項(xiàng)式歸約是指轉(zhuǎn)換函數(shù)f(x)不能太復(fù)雜辜膝，需要在多項(xiàng)式時間內(nèi)完成。如果是指數(shù)級或其他復(fù)雜度就沒有意義了漾肮。
符號是一個小于等于號加上下標(biāo)一個p代表多項(xiàng)式厂抖。
A多項(xiàng)式歸約B，意味著問題B至少和求解問題A一樣難克懊，意義跟小于等于號類似忱辅。
多項(xiàng)式歸約實(shí)際是用來比較解決兩個問題的難度大小關(guān)系。
多項(xiàng)式歸約的性質(zhì)
建立多項(xiàng)式可解性
B多項(xiàng)式可解則A也多項(xiàng)式可解谭溉。
建立建立難解關(guān)系(intractability)
A多項(xiàng)式不可解則B也多項(xiàng)式不可解墙懂。
建立等價性
A、B相互歸約夜只，則 A B兩個問題等價垒在。
多項(xiàng)式歸約的方法
具體如何做多項(xiàng)式歸約呢？
- 通過簡單等價性
- 通過一般情況歸約
- 通過編碼
簡單等價性
這里舉一個例子扔亥，一個問題是獨(dú)立集問題场躯，一個問題是頂點(diǎn)覆蓋問題。
獨(dú)立集：求一個子集S旅挤，頂點(diǎn)數(shù)>=k踢关，其各頂點(diǎn)之間相互獨(dú)立，沒有邊相連粘茄。
（假裝有圖）
k=6: 存在
k=7：不存在
頂點(diǎn)覆蓋：求一個子集S签舞，頂點(diǎn)數(shù)<=k，
（假裝有圖柒瓣，跟上一張圖一樣）
k=4:存在
k=3：不存在
兩個問題是一個等價問題儒搭，解是互補(bǔ)關(guān)系。
證明略芙贫。
一般情況歸約
這里同樣舉兩個例子搂鲫。
集合覆蓋(set cover)
設(shè)有一個所有元素的集合U，U有S1,S2,S3...Sm的元素子集磺平，是否存在<=k個子集的集合魂仍，他們的并集就是U拐辽。
頂點(diǎn)覆蓋問題
如上。
這兩個問題之間可以相互歸約擦酌，頂點(diǎn)覆蓋問題可以看做集合覆蓋問題的特殊情況俱诸。
即：U是所有邊的集合，每個子集相當(dāng)于一個頂點(diǎn)赊舶，子集內(nèi)是該頂點(diǎn)關(guān)聯(lián)的邊睁搭。
編碼
問題A和問題B的形式上差距很大，需要通過零件編碼(encode with gadgets)锯岖？
同樣舉兩個例子介袜。
布爾公式可滿足問題
布爾變量的析取構(gòu)成子句，子句的合取構(gòu)成公式出吹。
問題是：是否存在一組布爾變量滿足公式為真遇伞。
這個問題非常復(fù)雜，所以有一個簡化的問題：每個子句含有三個布爾變量捶牢，求公式的可滿足解鸠珠。 這就是3-SAT可滿足問題。
獨(dú)立集問題
如上秋麸。
兩個問題看起來差距很大（不是看起來好吧）渐排，但其實(shí)也是可以相互歸約的。
將3-SAT問題歸約成一個圖的獨(dú)立集問題
具體怎么編碼呢灸蟆？通過布爾公式構(gòu)造一個圖驯耻，圖怎么構(gòu)造呢？公式是由多個子句構(gòu)成炒考，每個子句構(gòu)成一個子圖可缚，所以每個子圖是一個三角形，有三個頂點(diǎn)對應(yīng)三個布爾變量斋枢。將每個變量和它的否定之間加一條邊帘靡，這樣就把邊加上去了。
（假裝有圖）
尋找可滿足解實(shí)際就是獨(dú)立集問題瓤帚，獨(dú)立集問題中的k取公式中子句的數(shù)量描姚，通過這樣一個構(gòu)造方式，3-SAT問題就被歸約成了一個圖的獨(dú)立集問題戈次。
我們需要證明這個歸約過程是有效的：證明：S如果是圖里的一個獨(dú)立集<--->可以找到一個可滿足解
證明
S如果是一個獨(dú)立集轩勘，那么S在這個圖里，每個三角形里最多包含一個頂點(diǎn)怯邪，否則不是獨(dú)立集绊寻。將所有這些點(diǎn)設(shè)置為true，則這個公式一定可以滿足。
反過來榛斯，如果是一個可滿足解，在每個子句里搂捧，選擇一個為true的文字量驮俗，將三角形里對應(yīng)的點(diǎn)選出來，這些點(diǎn)union起來就是一個獨(dú)立集允跑。
有了這個歸約技術(shù)以后王凑，則可以進(jìn)行問題之間難度的比較關(guān)系。歸約滿足傳遞性聋丝。
NP完全性
有了多項(xiàng)式歸約這個基礎(chǔ)索烹，就可以解釋NP完全性。之前討論算法時弱睦，經(jīng)常會討論到可以把一個很復(fù)雜的問題用一個巧妙的多項(xiàng)式方法解決百姓。實(shí)際上，有很多實(shí)際的問題况木，以目前的技術(shù)是很難給出有效的多項(xiàng)式解法垒拢，這些問題就是NP完全問題，代表困難問題火惊。比如0-1背包問題等求类。
特別關(guān)心哪些問題是屬于NP完全問題，要了解問題的難度屹耐，可以設(shè)計(jì)啟發(fā)式的算法尸疆、近似解、使用指數(shù)級復(fù)雜度算法惶岭。寿弱。
接下來討論三類問題
P類問題，NP問題俗他，NP完全問題脖捻。
Class P P類問題是代表一類問題，這個P代表Polynomia多項(xiàng)式,所有多項(xiàng)式時間內(nèi)可解的問題都屬于P類問題兆衅。比如常數(shù)時間地沮，分治法中的求中位數(shù)等。
不屬于P類問題的問題有intractable和unsolvable羡亩，比較經(jīng)典的不可解問題是圖靈停機(jī)問題摩疑，halting problem，給你任意一個算法和它的輸入畏铆，設(shè)計(jì)一個算法判斷它是否是無限循環(huán)雷袋，能否終止。
有些問題屬于難處理問題，難到什么程度呢楷怒？一個叫NP完全問題 一個叫NP困難問題蛋勺。
N:Nondeterministic，非確定性鸠删，算法的執(zhí)行過程是不確定的抱完。如果一個算法由兩個步驟構(gòu)成的，生成一個隨機(jī)解certificate刃泡，猜出一個隨機(jī)解巧娱，第二步進(jìn)行驗(yàn)證猜的解對不對。這樣一個算法稱為非確定性算法烘贴，第一個階段是不確定的禁添，第二個階段是確定的。
P：polynomia桨踪，驗(yàn)證階段是多項(xiàng)式的老翘。
P和NP是否相等？is P = NP ?
any problem in P is also in NP
NP屬于P還沒有證明锻离。
NP完全問題酪捡，NP問題里最難的問題，大多數(shù)實(shí)際問題要么是P問題要么是NP完全問題纳账，但P和NP都只是所有實(shí)際問題的子集逛薇。
B是NP完全問題，(1)B是NP問題疏虫，(2)所有屬于NP問題的A 都可以歸約成問題B永罚。
如果B只滿足(2)，則B是NP-hard問題卧秘。
目前沒有人證明NP是不能多項(xiàng)式可解呢袱，也沒人證明NP是多項(xiàng)式可解。
