看完兩個問題後，我覺得兩個問題的癥結點差不多
關鍵在於，我們如果想證明某個問題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亦可解
大概是這樣，希望有回答到你的問題
手機排版還請見諒
:

所以可以說 我們找的instance 不一定要跟題目完全一樣 或是不用for all condition 只要其中一種instance （像他cost 只取一種情況）可以多項式時間轉換 然後可以左邊對等價右邊對 就可以證明他 reduction 沒錯嗎我是卡在 他取的instance 感覺跟題目沒有完全吻合，甚至只有考慮部分情況（cost不可能只有那種形式） 為什麼可以得證所有條件都成立是不是這樣說：clique 那題找的instance 中的 k 其實跟原題的k沒關係，我們只是要找一個問題的轉換 這樣嗎？我有大概抓到一些感覺了 重點應該是要放在證明 B比A 難沒錯吧？只是我問題還是卡在instance的取法影響證明的正確性

第一個問題：不對，假設現在要證A reduce到B那我們要證的是 for all A的 instance，都能透過f轉換成B的instance，這個對A來講是for all都要成立的但是就像我說的，cost function只是reduce function的一部分，他跟A的instance無關，這是可以自己挑的你可以想想看，是不是隨便選一個graph，都能透過那條cost function，轉換成一個TSP的instance至於clique的k跟vertex cover的k還是有關係的，不能說完全沒關只是for all k都能找到如此的對應關係，所以就像你講的，重點在找到兩個問題的轉換，藉此證明誰比誰難

所以他取的 cost function 只是為了轉換後能得到他要的結果，跟原題給定的 cost function 沒關係，因為我們已經假定原題有解 只是要證明他不比HC簡單 這樣對嗎重新敘述一下好了：因為我們假定TSP能解了，只是要證他是NPC 我不用管他給的cost , k 是多少 反正要證他不比HC難就對了，所以從HC出發去找一種轉換 這樣對嗎

嗯嗯沒錯～就算是一個特例也沒關係因為本來就假設TSP能解了 只是想證明HC不比TSP難而已

但是問題還是得限定在 cost function 跟 k cost 沒錯吧只是我可以任意取我想要的合理轉換就是 instance 的部分