Re: [理工] 演算法 NP-complete證明

看板Grad-ProbAsk作者mi981027 (呱呱竹)時間3年前 (2020/09/01 11:15)推噓5(5推 0噓 29→)

留言34則, 2人參與討論串2/2 (看更多)

看完兩個問題後，我覺得兩個問題的癥結點差不多關鍵在於，我們如果想證明某個問題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://www.ptt.cc/bbs/Grad-ProbAsk/M.1598930120.A.9AD.html

推