参考：https://zhidao.baidu.com/question/68492427.html?qbl=relate_question_0&word=%B6%E0%CF%EE%CA%BD%CA%B1%BC%E4%C4%DA

https://blog.csdn.net/wxdsdtc831/article/details/7942435

?

?

什么是NP问题

概念1:

在计算机学科中，存在多项式时间的算法的一类问题，称之为P类问题；而像梵塔问题、推销员旅行问题、（命题表达式）可满足问题这类，至今没有找到多项式时间算法解的一类问题，称之为NP类问题。

?

?

?

?

?

就是问题需要的时间（复杂度）与问题的规模之间是多项式关系。
举个例子：

现在从n阶图中找两点的最短路径，复杂度为n^2级别（即O(n^2)），而n^2对于n是多项式（单项式当然也算），这就称为是多项式复杂度，或者多项式时间，其中问题（算法）的规模是n。

如果某一个算法的规模是n，但是复杂度比如是2^n，写不成n的多项式，那就不是多项式时间。

?