[理工] NP 問題

[Transfat (Transfat)]

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
→ FRAXIS: If A is NP-complete, A reduce to B, then B is NP-hard.
推 gary19941208: 因為B不一定在NP裡
可是B比A更難，A已經是NP-complete,B可能只是NP-hard but not NP?
→ k2shouai: Halting problem 是NP hard不是NP所以不對
推 qq70200: 請問這題答案是?  @@
→ s89162504: 1吧
推 mloop: 1 3應該都對 np complete也是np
→ mloop: 抱歉應該是錯的
→ mloop: 只會限制下限
推 s89162504: NP要另外證 poly reduce只能證NP hard
→ yupog2003: 我會想選(1)(3)耶！(3)我是想說A可以reduced from B,
→ yupog2003: 代表B比A簡單，A都只有NP-complete，B應該也是NP-compl
→ yupog2003: ete以下才對，所以也算NP？不知道觀念哪裡錯了
→ yupog2003: 看了這題才發現自己的觀念其實並不清楚...
→ Transfat: 我也沒有這題的答案，這是我小考的題目，所以才跟大家
→ Transfat: 討論一下
結論一下問題：
(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
推 FRAXIS: If A is NP, B is reduced to A, then B is NP.
→ FRAXIS: 這邊 reduction 是指 polynomial time karp reduction
→ yupog2003: FRAXIS大真是演算法難題救贖者，難題都會出現
→ HEroKuma: 3應該是對的, 如果A是NPC代表給一組解能在poly time驗證
→ HEroKuma: B能poly time內規約成A, 那B也能給解檢驗, 所以B is NP
→ HEroKuma: 筆記的部分, A reduction 'to' B, 可能會讓B不屬於NP
→ HEroKuma: 此時B為NP-hard