1. P类问题（Polynomial Problem）
P类问题是指一类能够用确定性算法在多项式时间内求解的判定问题。其实，在非正式的定义中，我们可以把那些在多项式时间内求解的问题当作P类问题。
2. NP类问题（Non-deterministic Polynomial Problem）
NP类问题不是非P类问题，他把问题分为猜测和验证。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可在多项式的时间里猜出一个解的问题。在某个题中，找一个解很困难 ，但验证一个解很容易。
NP类问题是指一类可以用不确定性多项式算法求解的判定问题。例如，旅行商问题（TSP，Traveling Salesman Problem）的判定版本就是一个NP类问题。我们虽然还不能找到一个多项式的确定性算法求解最小的周游路线，但是可以在一个多项式 时间内对任意生成的一条“路线”判定是否是合法（经过每个城市一 次且仅仅一次）。比较P类问题和NP类问题的定义，我们很容易得到 一个结论：PNP。
3. NP完全问题（NP Complete Problem）
我们称一个判定问题D是NP完全问题，条件是：
（1）D属于NP类；
（2）NP中的任何问题都能够在多项式时间内转化为D。
4. NP难问题（NP-hard Problem ）
另外，一个满足条件（2）但不满足条件（1）的问题被称为NP难问题。也就是说，NP难问题不一定是NP类问题， 正式地说，一个NP难问题至少跟NP完全问题一样难，也许更难！文章来源：https://www.toymoban.com/news/detail-492879.html
例如在某些任意大的棋盘游戏走出必胜的下法， 就是一个NP难的问题，这个问题甚至比那些NP完全问题还难。文章来源地址https://www.toymoban.com/news/detail-492879.html
到了这里，关于【简述】【图】P类问题、NP类问题、NP完全问题和NP难问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
