[理工] NP 問題

看板Grad-ProbAsk作者 (what?)時間13年前 (2012/03/19 00:29), 編輯推噓2(2推 0噓 13→)
留言15則, 5人參與, 最新討論串1/2 (看更多)
不好意思!想請問一下這題是不是為True? http://ppt.cc/Hb1o 我自己是覺得T但又解釋不出來!想麻煩版上的 大家可以幫我解一下嗎!謝謝! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.168.64.241
→
03/19 02:21, , 1F
是吧 因為NP間可以polynomial reduce過去?
03/19 02:21, 1F
推
03/19 08:12, , 2F
NO NP問題不一定是NP-Complete
03/19 08:12, 2F
→
03/19 08:17, , 3F
舉例來說, 每個在 P 中的問題都在 NP 中
03/19 08:17, 3F
→
03/19 10:26, , 4F
no
03/19 10:26, 4F
→
03/19 10:28, , 5F
P是NP 但NP不知道是不是P
03/19 10:28, 5F
→
03/19 11:12, , 6F
至所以不知道np是不是p是因為他有可能被解?只是目前
03/19 11:12, 6F
→
03/19 11:12, , 7F
還找不到答案嗎??
03/19 11:12, 7F
推
03/19 15:22, , 8F
一個問題在 NP 中代表我們可以在 P 時間內驗證一個"答案"
03/19 15:22, 8F
→
03/19 15:23, , 9F
是不是我們問題的解 一個問題是NP-Hard代表任何一個在NP中
03/19 15:23, 9F
→
03/19 15:23, , 10F
的問題都可以reduce到該NP-Hard的問題
03/19 15:23, 10F
→
03/19 15:25, , 11F
目前不知道是不是有一個問題在NP中但是他不在P當中
03/19 15:25, 11F
→
03/19 15:26, , 12F
若某個NP中的問題在P中，那所有可以在P時間內約到它的問題
03/19 15:26, 12F
→
03/19 15:27, , 13F
當然也是在P中. 但是不能在P時間內約到他的問題呢?不知道.
03/19 15:27, 13F
→
03/19 23:37, , 14F
對後 我把NP想成NP-complete了=.=
03/19 23:37, 14F
→
09/11 15:01, , 15F
當然也是在P中. 但是 https://daxiv.com
09/11 15:01, 15F
‣ 更多 aa23032311 的文章
文章代碼(AID): #1FPWs7df (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
理工
5
22
[理工] NP 問題 NP 問題
Transfat
9年前, 01/13
理工
2
15
[理工] NP 問題 NP 問題
aa23032311
13年前, 03/19
在新視窗開啟完整討論串 (共2篇)
‣ 更多 aa23032311 的文章
文章代碼(AID): #1FPWs7df (Grad-ProbAsk)