[理工] 演算法 NP問題

[newpuma (還很新)]

http://i.imgur.com/mvowQ7v.jpg
3-2這題該怎麽改才對呢？
non deterministic polynomial time嗎？

http://i.imgur.com/wAu4T2u.jpg
(1) 能被polynomial algo linear reduce不代表對方就有polynomial algo嗎？
(2) 是因為NPC不是NP的上界嗎
(3) 為什麼a的lower bound都確定了，沒辦法確定b的lower bound呢？

以上 謝謝大家

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.200.66
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485209945.A.FC9.html
推 gary19941208: 3-2你說的沒錯，是non deterministic polynomial.(1
→ gary19941208: )p1p2顛倒了(2)只能說NP有線性時間，搞不好他reduce
→ gary19941208: 的過程就花O(n^4)了(3)A是n^3，B是n也符合他說的上
→ gary19941208: 界規定，但下界就不對了，因為上界不夠tight
對耶B可以很小...因為只有上界限制，真的謝謝你，沒想到答案都睡不好了xd
※ 編輯: newpuma (223.137.200.66), 01/24/2017 07:44:47