看板 [ TransCSI ]
討論串[問題] NP problem& P problem?怎麼區分?
共 4 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] NP problem& P problem?怎麼區分?
推噓4(4推 0噓 2→)留言6則，0人參與, 最新作者dynamicy (小人物)時間19年前 (2005/06/13 23:29), 編輯資訊
2
0
0
內容預覽:
不是很懂這個怎麼區分?.... 可以麻煩那位解說一下,感謝!. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 218.174.207.179.
#2
Re: [問題] NP problem& P problem?怎麼區分?
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者aether982 (阿青是我是阿青)時間19年前 (2005/06/14 00:26), 編輯資訊
1
0
0
內容預覽:
P denotes the class of all problems that can be. solved by deterministic algorithms in polynomial. time.. NP denotes the class of all problems that ca
(還有178個字)
#3
Re: [問題] NP problem& P problem?怎麼區分?
推噓1(1推 0噓 0→)留言1則，0人參與, 最新作者flashstar (閃亮的星)時間19年前 (2005/06/14 16:05), 編輯資訊
0
0
0
內容預覽:
P: 可以用一個明確的演算法在polynomial time來解決. NP: 無法用一個明確的演算法在polynomail time來解決. 但可以在polynomail time來驗證所找的答案是對的或錯的. 即字面意思 P: polynomail time solveble.. NP: Nonp
#4
Re: [問題] NP problem& P problem?怎麼區分?
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者flashstar (閃亮的星)時間19年前 (2005/06/14 16:25), 編輯資訊
0
0
0
內容預覽:
在這邊NP寫的有點不清楚, 應該是要說, 像找Hamiton Cycle, 大家都知道這是一個. NP的問題, 意思是找Hamiton Cycle沒有明確的方法,. 但要驗證找出來的path是否為Hamiton Cycle則很容易,. 這在演算法中是可以reduce到SAT的問題, 而SAT則是簡單
首頁
上一頁
1
下一頁
尾頁