有爬过文了，不懂的点差不多，但旧的那篇还是看不懂
第一个是 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感觉又是随便取一个？