[理工] [演算法] P、NP、NPC問題

看板Grad-ProbAsk作者huangwh (香腸)時間12年前 (2012/02/27 00:42)推噓5(5推 0噓 0→)

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

題目是要回答T of F: 第1,2題:http://ppt.cc/2fWH 我認為答案為 F T ，但不確定是否正確第3,4題:http://ppt.cc/mu5b 我認為都為 T 但是在網路上有看到第3題的答案為:F 不過，我另外在網路上找到的資料寫說: >>若有一個NP-Complete Problem可以找到Polynomial Solution，則所有的NP問題都可以，也就是說NP=P >>若有一個NP-Complete Problem可以證明其Lower Bound為 Exponential time，則所有NP-Complete Problem的Lower Bound 均為Exponential time，也就是說NP!=P 所以不知道3,4題到底答案為何? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.115.241.250

推

Byzantin

02/27 07:52, , 1^F

02/27 07:52, 1^F

推

askaleroux

02/27 07:58, , 2^F

02/27 07:58, 2^F

推

FRAXIS

02/27 20:18, , 3^F

02/27 20:18, 3^F