[理工] NP 問題
Which of the following statements are correct. Justify your answers.
(1) If A is an NP-hard problem that can be reduced in polynomial time to problem B, then B is NP-hard.
(2) If A is an NP-hard problem that can be reduced in polynomial time to problem B, then B is NP-complete.
(3) If A is an NP-complete problem that can be reduced in polynomial time from problem B, then B is in NP.
(4) If A is an NP-hard problem that can be reduced in polynomial time from problem B, then B is in NP.
話說我看我之前上課的筆記，我抄到一個：If A is NP-complete, A reduce to B,then B is NP-complete
我現在看起來是對的，可是我那時候筆記寫不一定，例子是halting problem.
想問你們怎麼看
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484317348.A.1FB.html
→
01/13 22:29, , 1F
01/13 22:29, 1F
推
01/13 22:29, , 2F
01/13 22:29, 2F
可是B比A更難，A已經是NP-complete,B可能只是NP-hard but not NP?
→
01/13 22:36, , 3F
01/13 22:36, 3F
推
01/13 23:00, , 4F
01/13 23:00, 4F
→
01/13 23:22, , 5F
01/13 23:22, 5F
推
01/13 23:34, , 6F
01/13 23:34, 6F
→
01/13 23:35, , 7F
01/13 23:35, 7F
→
01/13 23:36, , 8F
01/13 23:36, 8F
推
01/13 23:39, , 9F
01/13 23:39, 9F
→
01/14 07:18, , 10F
01/14 07:18, 10F
→
01/14 07:19, , 11F
01/14 07:19, 11F
→
01/14 07:19, , 12F
01/14 07:19, 12F
→
01/14 07:20, , 13F
01/14 07:20, 13F
→
01/14 09:52, , 14F
01/14 09:52, 14F
→
01/14 09:52, , 15F
01/14 09:52, 15F
結論一下問題：
(1)對的，因為B比A更難，如果A已經是NP-hard,B也會是NP-hard
(2)錯的，B有可能只是NP-hard, 不是NP-complete
(3)對的(?)
(4)錯的，B可能是NP-hard,不是NP(?)
※ 編輯: Transfat (140.112.25.105), 01/14/2017 11:26:33
推
01/14 12:13, , 16F
01/14 12:13, 16F
→
01/14 12:13, , 17F
01/14 12:13, 17F
→
01/14 12:36, , 18F
01/14 12:36, 18F
→
01/15 03:27, , 19F
01/15 03:27, 19F
→
01/15 03:28, , 20F
01/15 03:28, 20F
→
01/15 03:30, , 21F
01/15 03:30, 21F
→
01/15 03:31, , 22F
01/15 03:31, 22F
討論串 (同標題文章)