看完两个问题后，我觉得两个问题的症结点差不多
关键在于，我们如果想证明某个问题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 的部分