有爬過文了，不懂的點差不多，但舊的那篇還是看不懂
第一個是 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 的vertex cover
他的instance 取法是
alpha為：用你原題的input（size=k）代入你找的NP-complete問題（clique ） 然後再推一個對應的原題欲證解答（beta）這樣嗎？
一開始我不太懂明明是要找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感覺又是隨便取一個？
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.8.161.10 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1598886442.A.BB9.html