作者mi981027 (呱呱竹)
看板Grad-ProbAsk
標題Re: [理工] 演算法 NP-complete證明
時間Tue Sep 1 11:15:18 2020
看完兩個問題後，我覺得兩個問題的癥結點差不多
關鍵在於，我們如果想證明某個問題B是NP-hard
要做的是，找到一個已知的NP-Complete問題 A，再證明A沒有比B難（B沒有比A簡單
）
怎麼證明A沒有比B難？
想法上是：說明“若B可解，則A也可以解”
這邊因果關係要分清楚，關鍵在我們可以把B的解法當成一個黑盒子，來說明，若我們擁
有這個黑盒子，則A就能透過這個黑盒子解出來
所以我們會想辦法把A的instance透過polynomial time 的 reduction, 轉成B的instance
除此之外，還要證明correctness
也就是必須證明若x為A的解 <=> f(x)為B的解 (假設f為reduce function)
那因為我們已經假設B可解了，所以A就可以解
所以簡言之，證明B為NP-Completeness應為以下步驟(幫你的說法做一點補充)
1. 證明B為NP
2. 證明B為"NP-hard"
2-1. 找一個已知的NP-completeness問題A
2-2. 找一個reduce function f, 可以把A的instance轉成B的instance
2-3. 證明x 為A的解 <=> f(x)為B的解
2-4. 說明f可以在polynomial time做轉換
這就是標準證明NP-completeness的SOP
※ 引述《NTUmaki (西木野真姬)》之銘言：
: 有爬過文了，不懂的點差不多，但舊的那篇還是看不懂
: 第一個是 vertex cover 問題
: https://i.imgur.com/hb4qJE9.jpg
: https://i.imgur.com/UfzNTcV.jpg
: 主要在證 alpha iff beta (instance)那邊有問題
: 想問下，原題是問有沒有size = k的 vertex 但後面變成證 有k 的clique 就會有 |V|
-k
重新釐清一下，這邊我們想證的NP-hard問題是vertex cover(簡記為B)，而利用的已知NP
-complete問題為clique(簡記為A)
根本來講，我們想證的是，若B可解，則A可解
現在A的instance x 是給定一張圖，詢問有無size為k的clique
而透過詳解的reduction，每一個這樣的問題，都可以被轉成一個B的instance f(x), 轉
而詢問有無|V| - k的vertex cover
記得因果關係，我們已經假設f(x)可以透過某個黑盒子解出來了
所以，只要我們證明 x為A的解 <=> f(x)為B的解
就證明“若B可解，則A亦可解”
也就證明了A -> B的reduction
: 他的instance 取法是
: alpha為：用你原題的input（size=k）代入你找的NP-complete問題（clique ） 然後
再?
: 一開始我不太懂明明是要找size=k 的 vertex cover 怎麼變成 size =k 的clique。但
後
: https://i.imgur.com/zaQsKLd.jpg
: 證明 NP-complete兩個步驟
: 1. 屬於NP ： 這個OK
: 2. 找一個NP-complete reduce 到該問題
: 然後證 reduce要證兩件事
: 1. 可以 polynomials transform : 這個OK
: 2. 找 instance 使得 alpha iff beta ：這邊我就完全不懂了。
: 首先從左到右： 把原圖的HC 補成complete之後 為什麼可以自己定cost function？
: 原題是問’某一個‘給定的 cost function （就像上面那題給size=k）為什麼取成解
答?
: 右到左：是因為 TSP 本來就定成HC 所以 trivial 嗎？
: 我覺得 找instance 那邊不是很懂怎麼取的
: 感覺有跟題目相關 但是TSP感覺又是隨便取一個？
一樣的問題，我們想把原本的instance x轉成TSP的instance f(x)
他定義的cost function也只是reduction的一部分
只要能轉成適當的TSP 問題，都是可以自己定義的
correctness 的部分
左到右的話，可以看看，如果x(原圖)具有HC
因為轉換後的圖，所有屬於原圖的邊，cost都是0
那是不是代表轉換後有一條TSP的路徑cost和為0
那f(x)就是 "G中是否存在一個cost至多為0的TSP問題" 的其中一個解
右到左雖然可以說是trivial，但有一些眉角要注意
我們想證明的是：若f(x)為TSP的解，則x為HC的解
注意我們方向上雖然是要證右到左，但你不能說：因為TSP的圖本來就是complete的，所
以本來就有HC
而是要說：透過f轉換而成的f(x)如果是TSP的解，則x是HC的解
所以正確的說明應該是：假設透過f轉換而成的f(x)具有cost和為0的TSP解
那這條路徑上的所有edge都在原圖 x 上
所以原圖 x 具有HC
在假設TSP問題可解的情況下
因為我們已經證明x為HC的解 <=> f(x)為TSP的解
所以HC亦可解
大概是這樣，希望有回答到你的問題
手機排版還請見諒
: -----
: Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.75.13 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1598930120.A.9AD.html
1F：推 NTUmaki: 所以可以說 我們找的instance 不一定要跟題目完全一樣 或 09/01 15:36
2F：→ NTUmaki: 是不用for all condition 只要其中一種instance （像他co09/01 15:36
3F：→ NTUmaki: st 只取一種情況）可以多項式時間轉換 然後可以左邊對等09/01 15:36
4F：→ NTUmaki: 價右邊對 就可以證明他 reduction 沒錯嗎09/01 15:36
5F：→ NTUmaki: 我是卡在 他取的instance 感覺跟題目沒有完全吻合，甚至09/01 15:37
6F：→ NTUmaki: 只有考慮部分情況（cost不可能只有那種形式） 為什麼可以09/01 15:37
7F：→ NTUmaki: 得證所有條件都成立09/01 15:37
8F：推 NTUmaki: 是不是這樣說：clique 那題找的instance 中的 k 其實跟原09/01 15:46
9F：→ NTUmaki: 題的k沒關係，我們只是要找一個問題的轉換 這樣嗎？09/01 15:46
10F：推 NTUmaki: 我有大概抓到一些感覺了 重點應該是要放在證明 B比A 難09/01 15:49
11F：→ NTUmaki: 沒錯吧？只是我問題還是卡在instance的取法影響證明的正09/01 15:49
12F：→ NTUmaki: 確性09/01 15:49
13F：→ mi981027: 第一個問題：不對，假設現在要證A reduce到B09/01 17:43
14F：→ mi981027: 那我們要證的是 for all A的 instance，都能透過f轉換09/01 17:43
15F：→ mi981027: 成B的instance，這個對A來講是for all都要成立的09/01 17:43
16F：→ mi981027: 但是就像我說的，cost function只是reduce function的一09/01 17:43
17F：→ mi981027: 部分，他跟A的instance無關，這是可以自己挑的09/01 17:43
18F：→ mi981027: 你可以想想看，是不是隨便選一個graph，都能透過那條cos09/01 17:43
19F：→ mi981027: t function，轉換成一個TSP的instance09/01 17:43
20F：→ mi981027: 至於clique的k跟vertex cover的k還是有關係的，不能說09/01 17:44
21F：→ mi981027: 完全沒關09/01 17:44
22F：→ mi981027: 只是for all k都能找到如此的對應關係，所以就像你講的 09/01 17:44
23F：→ mi981027: ，重點在找到兩個問題的轉換，藉此證明誰比誰難 09/01 17:44
24F：推 NTUmaki: 所以他取的 cost function 只是為了轉換後能得到他要的結09/01 22:39
25F：→ NTUmaki: 果，跟原題給定的 cost function 沒關係，因為我們已經假09/01 22:39
26F：→ NTUmaki: 定原題有解 只是要證明他不比HC簡單 這樣對嗎09/01 22:39
27F：→ NTUmaki: 重新敘述一下好了：因為我們假定TSP能解了，只是要證他是09/01 22:41
28F：→ NTUmaki: NPC 我不用管他給的cost , k 是多少 反正要證他不比HC難09/01 22:41
29F：→ NTUmaki: 就對了，所以從HC出發去找一種轉換 這樣對嗎09/01 22:41
30F：→ mi981027: 嗯嗯沒錯～就算是一個特例也沒關係09/01 22:48
31F：→ mi981027: 因為本來就假設TSP能解了 只是想證明HC不比TSP難而已09/01 22:48
32F：推 NTUmaki: 但是問題還是得限定在 cost function 跟 k cost 沒錯吧09/01 23:53
33F：→ NTUmaki: 只是我可以任意取我想要的合理轉換09/01 23:53
34F：→ NTUmaki: 就是 instance 的部分09/01 23:54
※ 編輯: mi981027 (49.216.75.13 臺灣), 09/02/2020 03:34:00