1200字范文,内容丰富有趣,写作的好帮手!
1200字范文 > 【NP问题】P问题 NP问题 NPC问题 NPH问题

【NP问题】P问题 NP问题 NPC问题 NPH问题

时间:2022-11-05 06:29:19

相关推荐

【NP问题】P问题 NP问题 NPC问题 NPH问题

P类问题:

官方定义:所有可以在多项式时间内求解的判定问题。(判定问题:判断是否有一种能够解决某一类问题的能行算法的研究课题。)

自己的理解:对于一类问题,能有一个确定性算法,在多项式时间内就能解出所有答案。

例如:冒泡排序、快速排序等问题。

NP类问题:

官方定义:所有的非确定性多项式时间可解的判定问题构成NP类问题。(非确定性算法:非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的,算法的验证阶段是确定性的,它验证猜测阶段给出解的正确性。)

自己的理解:对于一类问题,我们无法找到一个确定性算法,在多项式时间内解出所有答案。但是,存在一个非确定性算法,能够猜出某个答案,然后,有一个确定性算法,能在多项式时间内验证这个答案是否正确。一个NP问题,它的某个答案,能在多项式时间内验证是否正确。

例如:大数分解问题,比如找到180576这个数的因数,可能很久都解不出来,但是我告诉你这是352513得到的(非确定性的猜测),那么很容易就能在多项式时间内验证是否正确(确定性的验证,352513很容易计算),这就是NP问题。

NPC类问题:

官方定义:NP中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的。

自己的理解:对于一个NP问题,如果其他所有NP问题都可以通过一个多项式时间的算法转化成它,这个问题就是NP完全问题。或者说,一个NPC问题,它的所有答案,都能在多项式时间内验证是否正确。

NPH类问题:NP困难问题不一定是一个NP问题,但是其他所有NP问题都可以通过一个多项式时间的算法转化成它。

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。