[理工] [演算法] P, NP, NP-complete文氏圖

[YuxiWen (yu)]

以下是我對P, NP, NP-complete, NP-complete集合的交集情況的理解，
不知道這樣是不是對的?
有錯請糾正，謝謝!
http://i.imgur.com/vEuAPtO.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.164.15
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485158341.A.70B.html
推 yupog2003: P =\= NP那張，P應該也要在NP裡面才對
推 EasonGod: P在NP裡面吧
     對耶，我想錯了，
謝謝，兩位的提醒
→ yupog2003: P = NP那張，NP-complete也會等於P和NP
    請問為什麼?
NP-complete不是要屬於NP且為NP-hard的問題嗎
推 EasonGod: 話說各間學校考試有考過co-NP這個概念嗎？
※ 編輯: YuxiWen (114.137.164.15), 01/23/2017 16:06:06
※ 編輯: YuxiWen (114.137.164.15), 01/23/2017 16:08:23
→ yupog2003: P=NP=NP-complete ⊆NP-hard也可以滿足NP-complete的定
→ yupog2003: 義
→ yupog2003: 參考一下：http://i.imgur.com/4IWiniT.jpg
     我就是看到這一頁不太懂XD
     看了很久，還是不知道為什麼NP-complete可以大到跟NP一樣多?
→ yupog2003: 可能我做的考古題還不夠多，目前沒看到co-NP的題目
※ 編輯: YuxiWen (114.137.164.15), 01/23/2017 16:40:04
→ ken52011219: 因為 NPC ∈ NP , 若 P = NP =>  NPC⊆NP = P
→ ken52011219: 這邊指的是 NP 時間可以由 P 時間內解決了話
→ ken52011219: NP-Complete 也因為屬於 NP 時間 因此可被 P 時間內
→ ken52011219: 解決
    原來如此，終於懂了，非常感謝ken大的解惑!!!
※ 編輯: YuxiWen (223.140.76.224), 01/23/2017 19:08:01
推 newpuma: 請問P不等於NP時 NPC還會等於NP嗎
→ newpuma: P=NP時 可以直接推得所有P問題都是NPC嗎？
→ yupog2003: P不等於NP時，NPC就不會等於NP，但是會包含於NP
→ newpuma: 承上 這樣所有P、NP不就都包含於NP-hard？
→ yupog2003: P=NP時應該就可以直接推得所有P問題都是NPC
→ yupog2003: 看圖來說好像是這樣沒錯，等待高手解答
推 newpuma:  http://i.imgur.com/XMThEIV.jpg
→ newpuma: 這樣這題應該是T嗎？！
→ yupog2003: 應該是T，我寫考古的時候也是寫T
推 FRAXIS: 直覺上來說 P = NP 時， P = NP = NPC
→ FRAXIS: 但是數學上來說 P 裡面包含了兩個很特殊的問題
→ FRAXIS: 一個是無論如何輸出都是 yes 一個是無論如何輸出都是 no
→ FRAXIS: 這兩個問題沒辦法是 NPC (因為沒辦法建立 reduction）
推 FRAXIS: https://goo.gl/shLqO1
推 yupog2003: 推F大，感覺很多問題真的細究下去答案不一定是我們想的
→ yupog2003: 這樣，現在學的都好皮毛