作者AAQ8 ()
看板Grad-ProbAsk
标题[理工] 106中央资工演算法
时间Mon Jan 21 17:57:20 2019
https://i.imgur.com/HVeWcku.jpg
有爬过版上105中央资工的文章
题目有点不一样
不知道我这写对不对
(a)problem X存在polynomial-time reduction将problem X reduce到problem Y，则prob
lem Y为NP-hard。
(b)若problem Y存在一个演算法在polynomial-time时间内解出，则problem Y为NP。
麻烦各位一下
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.9.163.6
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548064643.A.E8A.html
1F：→ z3588191: A应该要多写X为NP01/21 18:10
2F：→ z3588191: B应该是说Y的解可以在poly-time内verify01/21 18:13
3F：→ z3588191: 你B写的是P的定义01/21 18:13
(a)若problem X可被non-deterministic algo在多项式时间内解决，且存在polynomial-t
ime reduction将problem X reduce到problem Y，则problem Y为NP-hard。
(b)若problem Y存在一个non-deterministic algo在polynomial-time时间内解出，则pro
blem Y为NP。
是修改成这样吗
※ 编辑: AAQ8 (39.9.163.6), 01/21/2019 18:30:34
4F：→ krusnoopy: (a)为啥X还要说是NP 不是都说X是NPC了 01/21 19:09
5F：推 skyHuan: a题目已经说X是NPC了，原本写那样应该不用改吧(? 01/21 19:09
6F：→ skyHuan: b改完之後应该是对的~ 01/21 19:10
7F：推 z3588191: 说明NPC为NP比较完整一些吧 01/21 20:13
8F：推 skyHuan: NPC一定是NP啊... 01/21 21:32
9F：推 krusnoopy: 不是阿 你还不如讲说因为X是NP-hard 你只拿一个NP问题 01/21 21:38
10F：→ krusnoopy: 来做reduction 证明又不成立 01/21 21:38
11F：推 krusnoopy: 要证明NP-hard 不一定要拿NPC来做reduction 但是一定 01/21 21:45
12F：→ krusnoopy: 要拿NP-hard问题来做 01/21 21:45
14F：→ skyHuan: 所以要证一个问题是NP-hard 01/21 22:33
15F：→ skyHuan: 法1. 根据定义证"所有"NP都reduce到他 01/21 22:33
16F：→ skyHuan: 法2. 找"一个"NPC问题reduce到他 01/21 22:33
17F：→ krusnoopy: 找一个NP-hard reduce也可以 01/21 22:38
18F：推 skyHuan: 对XD 可是课本只有教NPC的reduce就快崩溃了QQ 01/21 22:44
19F：→ skyHuan: 其实用NPC reduce也是NP hard的概念(?) 他也是NP hard 01/21 22:44
20F：→ krusnoopy: 对 所以我才说 与其讲NP 还不如讲是NP-hard 01/21 22:46
21F：→ krusnoopy: 有些NP-hard问题不是NPC 所以我觉得讲清楚点比较好～ 01/21 22:47
22F：→ krusnoopy: 这题我还是觉得知道X是NPC就够了 不用特别写 01/21 22:48