推 wardiry:映像中好像是有辦法以演算法處理跟無法以演算法댠 59.114.171.38 06/13
→ wardiry:處理的問題 59.114.171.38 06/13
→ wardiry:前後順序掉一下~~我不曉得我的解釋對不對 59.114.171.38 06/13
推 hicoy:請問一下那NP-complete又是什麼?140.121.203.164 06/14
推 flashstar:P和NP交集的那一塊稱為NP-Complete 61.224.77.77 06/14
推 flashstar:講錯講錯...可以E文的人麻煩E一下... 61.224.77.77 06/14
> -------------------------------------------------------------------------- <
作者: aether982 (阿青是我是阿青) 看板: TransCSI
標題: Re: [問題] NP problem& P problem?怎麼區分?
時間: Tue Jun 14 00:27:15 2005
※ 引述《dynamicy (小人物)》之銘言：
: 不是很懂這個怎麼區分?...
: 可以麻煩那位解說一下,感謝!
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 can be
solved by nondeterministic algorithms in polynomial
time.
A nondeterministic algorithm, when faced with a
choice of several options, has the power to guess
the right one (if there is any).
We will focus on decision problems, whose answer
is either yes or no.
演算法上課的講義
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.85.140
> -------------------------------------------------------------------------- <
作者: flashstar (閃亮的星) 看板: TransCSI
標題: Re: [問題] NP problem& P problem?怎麼區分?
時間: Tue Jun 14 16:11:19 2005
※ 引述《dynamicy (小人物)》之銘言：
: 不是很懂這個怎麼區分?...
: 可以麻煩那位解說一下,感謝!
P: 可以用一個明確的演算法在polynomial time來解決
NP: 無法用一個明確的演算法在polynomail time來解決
但可以在polynomail time來驗證所找的答案是對的或錯的
即字面意思 P: polynomail time solveble.
NP: Nonpolynomail time solveble, but Polynomail time verify.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.72.144
推 dynamicy:謝謝你的解答! 218.170.46.177 06/14
> -------------------------------------------------------------------------- <
作者: flashstar (閃亮的星) 看板: TransCSI
標題: Re: [問題] NP problem& P problem?怎麼區分?
時間: Tue Jun 14 16:30:07 2005
※ 引述《aether982 (阿青是我是阿青)》之銘言：
: ※ 引述《dynamicy (小人物)》之銘言：
: : 不是很懂這個怎麼區分?...
: : 可以麻煩那位解說一下,感謝!
: 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 can be
: solved by nondeterministic algorithms in polynomial
: time.
: A nondeterministic algorithm, when faced with a
: choice of several options, has the power to guess
: the right one (if there is any).
: We will focus on decision problems, whose answer
: is either yes or no.
: 演算法上課的講義
在這邊NP寫的有點不清楚, 應該是要說, 像找Hamiton Cycle, 大家都知道這是一個
NP的問題, 意思是找Hamiton Cycle沒有明確的方法,
但要驗證找出來的path是否為Hamiton Cycle則很容易,
這在演算法中是可以reduce到SAT的問題, 而SAT則是簡單的sum of product邏輯,
故可以在polynomail time 去 verify出true or false.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.77.77
推 aether982:謝謝你 我會去跟老師反應一下 ^^ 61.228.84.234 06/14
→ flashstar:不客氣...因為今年剛考完研究所, 還蠻熟的@@" 61.224.77.77 06/14