在算法学习的总结过程中，NP问题的研究常常会让我不太理解。趁着这次对软考算法学习的总结，再次翻看书页修订自己的知识网。
在学习中，会发现 P类问题、NP类问题、 NP-Hard 问题等 区分。为了对它们之间的关系有一个直观的认识，所以附上一张图。
由于数学家们无法证明P=NP 所以，会有两种情况下的关系：
P问题(Polynomial,多项式).P问题是可以在多项式时间内被确定机(通常意义的计算机)解决的问题。
NP问题是指非确定性多项式（non-deterministic polynomial，缩写NP）。所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可解决的问题。
NP-hard是其解的正确性能够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。相应的，若NP中所有问题到某一个问题是图灵可归约的，则该问题为NP困难问题。
以上描述来自一些专业研究者的描述，下面说说我自己的认识：
P类问题: 能在多项式时间内判定数据库是否有用户1信息。
NP类问题: 能在多项式时间内判定你已有的信息（如：用户1）是否证明了这个问题（用户1信息存在数据库）。
一点点深入学习了解其中的内涵，荣幸与您分享~
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/144099.html
