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

看板Grad-ProbAsk作者 (yu)時間9年前 (2017/01/23 15:59), 9年前編輯推噓8(8推 0噓 20→)
留言28則, 5人參與, 最新討論串1/1
以下是我對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
推
01/23 16:00, , 1F
P =\= NP那張，P應該也要在NP裡面才對
01/23 16:00, 1F
推
01/23 16:00, , 2F
P在NP裡面吧
01/23 16:00, 2F
對耶，我想錯了， 謝謝，兩位的提醒
→
01/23 16:01, , 3F
P = NP那張，NP-complete也會等於P和NP
01/23 16:01, 3F
請問為什麼? NP-complete不是要屬於NP且為NP-hard的問題嗎
推
01/23 16:02, , 4F
話說各間學校考試有考過co-NP這個概念嗎？
01/23 16:02, 4F
※ 編輯: YuxiWen (114.137.164.15), 01/23/2017 16:06:06 ※ 編輯: YuxiWen (114.137.164.15), 01/23/2017 16:08:23
→
01/23 16:11, , 5F
P=NP=NP-complete ⊆NP-hard也可以滿足NP-complete的定
01/23 16:11, 5F
→
01/23 16:11, , 6F
義
01/23 16:11, 6F
→
01/23 16:14, , 7F
01/23 16:14, 7F
我就是看到這一頁不太懂XD 看了很久，還是不知道為什麼NP-complete可以大到跟NP一樣多?
→
01/23 16:16, , 8F
可能我做的考古題還不夠多，目前沒看到co-NP的題目
01/23 16:16, 8F
※ 編輯: YuxiWen (114.137.164.15), 01/23/2017 16:40:04
→
01/23 17:07, , 9F
因為 NPC ∈ NP , 若 P = NP => NPC⊆NP = P
01/23 17:07, 9F
→
01/23 17:15, , 10F
這邊指的是 NP 時間可以由 P 時間內解決了話
01/23 17:15, 10F
→
01/23 17:15, , 11F
NP-Complete 也因為屬於 NP 時間 因此可被 P 時間內
01/23 17:15, 11F
→
01/23 17:15, , 12F
解決
01/23 17:15, 12F
原來如此，終於懂了，非常感謝ken大的解惑!!! ※ 編輯: YuxiWen (223.140.76.224), 01/23/2017 19:08:01
推
01/23 19:45, , 13F
請問P不等於NP時 NPC還會等於NP嗎
01/23 19:45, 13F
→
01/23 19:46, , 14F
P=NP時 可以直接推得所有P問題都是NPC嗎？
01/23 19:46, 14F
→
01/23 19:47, , 15F
P不等於NP時，NPC就不會等於NP，但是會包含於NP
01/23 19:47, 15F
→
01/23 19:47, , 16F
承上 這樣所有P、NP不就都包含於NP-hard？
01/23 19:47, 16F
→
01/23 19:48, , 17F
P=NP時應該就可以直接推得所有P問題都是NPC
01/23 19:48, 17F
→
01/23 19:48, , 18F
看圖來說好像是這樣沒錯，等待高手解答
01/23 19:48, 18F
推
01/23 19:50, , 19F
01/23 19:50, 19F
→
01/23 19:50, , 20F
這樣這題應該是T嗎？！
01/23 19:50, 20F
→
01/23 19:55, , 21F
應該是T，我寫考古的時候也是寫T
01/23 19:55, 21F
推
01/23 20:54, , 22F
直覺上來說 P = NP 時， P = NP = NPC
01/23 20:54, 22F
→
01/23 20:55, , 23F
但是數學上來說 P 裡面包含了兩個很特殊的問題
01/23 20:55, 23F
→
01/23 20:55, , 24F
一個是無論如何輸出都是 yes 一個是無論如何輸出都是 no
01/23 20:55, 24F
→
01/23 20:56, , 25F
這兩個問題沒辦法是 NPC (因為沒辦法建立 reduction）
01/23 20:56, 25F
推
01/23 21:03, , 26F
01/23 21:03, 26F
推
01/23 21:08, , 27F
推F大，感覺很多問題真的細究下去答案不一定是我們想的
01/23 21:08, 27F
→
01/23 21:08, , 28F
這樣，現在學的都好皮毛
01/23 21:08, 28F
‣ 更多 YuxiWen 的文章
文章代碼(AID): #1OXRV5SB (Grad-ProbAsk)