作者seafoodccu (c-看看你)
看板Grad-ProbAsk
标题[理工] 107 成大 程设
时间Mon Dec 14 23:30:07 2020
https://i.imgur.com/B1IhQiS.jpg
想问一下这题，我的想法是所有NP问题因为都不难於NP-hard问题，所以都可以在p时间内
reduce到NP-hard
而题目说到NP-hard具P时间可解，那是否代表P=NP=NPC=NP-hard呢？还是仅有P=NP=NPC而
已？
谢谢！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 112.104.18.31 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1607959809.A.743.html
1F：推 asd3136396: 我觉得是全部在同一个集合12/15 00:00
2F：→ mathtsai: NP-H可解->NP-C可解-> P = NP12/15 01:43
3F：→ mathtsai: NP-C会包含在 P=NP 里12/15 01:46
我的想法是NP-C和NP-H差别是在能不能在P时间内被验证，那如果题目提及NP-C可在P时间
内被解，是否等同说了NP-H能在P时间内被验证？这样NP-C和NP-H是否就属同样集合呢？
观念有误再麻烦纠正！谢谢！
※ 编辑: seafoodccu (223.138.43.120 台湾), 12/15/2020 08:02:50
5F：推 alex391a: Np hard 会在p 但因为定义不会在np(虽然这很怪）https:/12/15 09:27
6F：→ alex391a: /i.imgur.com/GRbdGsX.jpg12/15 09:27
8F：→ alex391a: 全部问题都可以用p解决 但np hard不能用p验证 所以 npc=12/15 09:28
9F：→ alex391a: np 12/15 09:28
10F：推 alex391a: 楼上那样画的话np hard就没在p里面了 我这样理解应该没12/15 09:31
11F：→ alex391a: 有错吧 12/15 09:31
a大我想问一下，为什麽NP-H都可以在p时间内解了，却不能用p验证？解出解来不就也是
验证了解对不对吗？
※ 编辑: seafoodccu (112.104.18.31 台湾), 12/15/2020 09:52:24
12F：推 alex391a: 我想想我应该想错了 npc也是np hard 所以应该是只是跟讲12/15 10:11
13F：→ alex391a: 义常出现的那个np=npc=p12/15 10:11
14F：→ alex391a: 所以其实题目应该跟 npc有p解 是等价的 可以讨论看看12/15 10:14
15F：→ mathtsai: a大画的好像比较对 我那样画NP-H就不会是P了 12/15 13:44
16F：→ mathtsai: 我的要把NP-H也加进P的范围才行 12/15 13:45
所以，NP-H就算能在P时间内解出，也不代表它能在P时间内验证答案吗？
※ 编辑: seafoodccu (112.104.18.31 台湾), 12/15/2020 14:22:24
17F：→ mathtsai: 不确定耶 能在P时间解出却不能被验证 感觉也很怪 12/15 14:29
18F：推 FRAXIS: 题目只是说有一个 NP-Hard 问题可以 P 时间解 12/17 11:18
19F：→ FRAXIS: 不是说所有 NP-Hard 可以在 P 时间内解 12/17 11:19
20F：→ FRAXIS: 所以就只能得到 P = NP = NP 12/17 11:20
21F：→ FRAXIS: P = NP, 而且 P=NP 比 NPC 多两个问题 12/17 11:22
23F：→ mathtsai: 抱歉 没看到只说一个 那就是只能得到P=NP 12/17 13:25