有爬过文了，不懂的点差不多，但旧的那篇还是看不懂 第一个是 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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1598886442.A.BB9.html