[理工] 演算法 NP問題

看板Grad-ProbAsk作者newpuma (還很新)時間9年前 (2017/01/24 06:19)推噓1(1推 0噓 3→)

留言4則, 1人參與討論串1/1

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

01/24 07:37, , 1^F

01/24 07:37, 1^F

→

gary19941208

01/24 07:37, , 2^F

01/24 07:37, 2^F

→

gary19941208

01/24 07:37, , 3^F

01/24 07:37, 3^F