作者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
1F：推 aether982:谢谢你 我会去跟老师反应一下 ^^ 61.228.84.234 06/14
2F：→ flashstar:不客气...因为今年刚考完研究所, 还蛮熟的@@" 61.224.77.77 06/14