当前位置：新励学网 > 秒知问答 > np 算法

np 算法

发表时间：2024-07-28 00:22:39 来源：网友投稿

NP，即非确定性多项式 Non-deterministic polynomial的缩写。所谓非确定性，就是指可以用一定数量的运算去解决多项式时间内可解决的问题。NP 问题通俗来说是其解的正确性能够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。相应的若NP中所有问题到某一个问题是图灵可归约的，则该问题为NP困难问题（NP-Hard或NPH），反之则为NP完全问题（NP-Complete或NPC）。

NP问题是一类可在多项式时间内验证你给出的答案是否正确的问题， P问题为NP问题的一个子类。

而NP-完全问题则是一类目前大家认为没有多项式算法去解决的问题，但是如果你给出了这类问题的一个答案，我可以在多项式时间内验证给出的答案是否正确。

NP-困难问题指的是至少和NP完全问题一样难的问题。注意NP-困难问题有可能比NP完全问题难，但却不会比它容易。

它们之间的关系：NP完全问题是NP问题的一个子类，它是NP问题中最难的一类问题。NP-困难问题和NP-完全问题有交集，但并不同，它还包含一类比NP完全问题更难的问题。

有关猜想

克雷数学研究所悬赏给出的21世纪七大数学猜想，其中有一个问题即为 P与NP问题的等价问题。

免责声明：本站发布的教育资讯（图片、视频和文字）以本站原创、转载和分享为主，文章观点不代表本网站立场。

如果本文侵犯了您的权益，请联系底部站长邮箱进行举报反馈，一经查实，我们将在第一时间处理，感谢您对本站的关注！