[理工] 演算法 NP-complete

[NTUmaki (西木野真姬)]

定理 6-1
若存在一個NP-complete 問題 為 polynomial-time solvable 則 P=NP

老師上課的說法是 NP裡面最難的問題可以多項式時間內解決，所以NP 包含於 P  ，然後P本來就包含於NP，得證。


我的詳細證明想法是這樣，不知道對不對

存在一個NP-complete為 P

NP-complete為屬於NP且為NP-hard
NP-hard 是 所有NP 都可以被polynomially reduce 到它

所以如果他是polynomials-time solvable 則所有NP問題都可以polynomially reduce 成它 再 polynomials solve it  因此所有NP包含於P



-----
Sent from JPTT on my iPhone

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.8.161.10 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1598872594.A.174.html
推 mi981027: 是的
→ NTUmaki: 順便問一下 這邊是不是多打complete?https://i.imgur.com
→ NTUmaki: /PTDJh9s.jpg
→ NTUmaki: https://i.imgur.com/ig3Irbg.jpg
→ NTUmaki: 鉛筆圈起來的地方，應該是想說所有NP都可以reduce到A 所
→ NTUmaki: 以也可以reduce到 B 因此得證B是NP-hard?
→ NTUmaki: 根據NP-hard定義看的話應該是多打complete 還是我哪邊搞
→ NTUmaki: 錯
→ mi981027: 嗯嗯對 這邊應該是對於所有C屬於NP 他多打了
→ mi981027: 不過依照定義來看 他這樣打也不算出錯