作者mi981027 (呱呱竹)
看板Grad-ProbAsk
标题Re: [理工] 演算法 NP-complete证明
时间Tue Sep 1 11:15:18 2020
看完两个问题後，我觉得两个问题的症结点差不多
关键在於，我们如果想证明某个问题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亦可解
大概是这样，希望有回答到你的问题
手机排版还请见谅
: -----
: Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 49.216.75.13 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1598930120.A.9AD.html
1F：推 NTUmaki: 所以可以说 我们找的instance 不一定要跟题目完全一样 或 09/01 15:36
2F：→ NTUmaki: 是不用for all condition 只要其中一种instance （像他co09/01 15:36
3F：→ NTUmaki: st 只取一种情况）可以多项式时间转换 然後可以左边对等09/01 15:36
4F：→ NTUmaki: 价右边对 就可以证明他 reduction 没错吗09/01 15:36
5F：→ NTUmaki: 我是卡在 他取的instance 感觉跟题目没有完全吻合，甚至09/01 15:37
6F：→ NTUmaki: 只有考虑部分情况（cost不可能只有那种形式） 为什麽可以09/01 15:37
7F：→ NTUmaki: 得证所有条件都成立09/01 15:37
8F：推 NTUmaki: 是不是这样说：clique 那题找的instance 中的 k 其实跟原09/01 15:46
9F：→ NTUmaki: 题的k没关系，我们只是要找一个问题的转换 这样吗？09/01 15:46
10F：推 NTUmaki: 我有大概抓到一些感觉了 重点应该是要放在证明 B比A 难09/01 15:49
11F：→ NTUmaki: 没错吧？只是我问题还是卡在instance的取法影响证明的正09/01 15:49
12F：→ NTUmaki: 确性09/01 15:49
13F：→ mi981027: 第一个问题：不对，假设现在要证A reduce到B09/01 17:43
14F：→ mi981027: 那我们要证的是 for all A的 instance，都能透过f转换09/01 17:43
15F：→ mi981027: 成B的instance，这个对A来讲是for all都要成立的09/01 17:43
16F：→ mi981027: 但是就像我说的，cost function只是reduce function的一09/01 17:43
17F：→ mi981027: 部分，他跟A的instance无关，这是可以自己挑的09/01 17:43
18F：→ mi981027: 你可以想想看，是不是随便选一个graph，都能透过那条cos09/01 17:43
19F：→ mi981027: t function，转换成一个TSP的instance09/01 17:43
20F：→ mi981027: 至於clique的k跟vertex cover的k还是有关系的，不能说09/01 17:44
21F：→ mi981027: 完全没关09/01 17:44
22F：→ mi981027: 只是for all k都能找到如此的对应关系，所以就像你讲的 09/01 17:44
23F：→ mi981027: ，重点在找到两个问题的转换，藉此证明谁比谁难 09/01 17:44
24F：推 NTUmaki: 所以他取的 cost function 只是为了转换後能得到他要的结09/01 22:39
25F：→ NTUmaki: 果，跟原题给定的 cost function 没关系，因为我们已经假09/01 22:39
26F：→ NTUmaki: 定原题有解 只是要证明他不比HC简单 这样对吗09/01 22:39
27F：→ NTUmaki: 重新叙述一下好了：因为我们假定TSP能解了，只是要证他是09/01 22:41
28F：→ NTUmaki: NPC 我不用管他给的cost , k 是多少 反正要证他不比HC难09/01 22:41
29F：→ NTUmaki: 就对了，所以从HC出发去找一种转换 这样对吗09/01 22:41
30F：→ mi981027: 嗯嗯没错～就算是一个特例也没关系09/01 22:48
31F：→ mi981027: 因为本来就假设TSP能解了 只是想证明HC不比TSP难而已09/01 22:48
32F：推 NTUmaki: 但是问题还是得限定在 cost function 跟 k cost 没错吧09/01 23:53
33F：→ NTUmaki: 只是我可以任意取我想要的合理转换09/01 23:53
34F：→ NTUmaki: 就是 instance 的部分09/01 23:54
※ 编辑: mi981027 (49.216.75.13 台湾), 09/02/2020 03:34:00