找到一些有趣的定义:

解释P和NP的最简单的方法是比较“文字问题”和“多项选择题”。

当你试图解决一个“应用题”时，你必须从头开始寻找解决方案。 当你试图解决一个“多项选择题”时，你有一个选择:要么像解决“应用题”一样解决它，要么试着把给你的每个答案都代入，然后选择一个合适的候选答案。

通常情况下，“多项选择题”比相应的“应用题”容易得多:替换候选答案并检查它们是否合适，可能比从头开始寻找正确答案要省力得多。

现在，如果我们同意花费多项式时间的努力是“简单”的，那么P类将由“简单的应用题”组成，NP类将由“简单的多项选择题”组成。

P和NP的本质是一个问题:“有没有简单的选择题不像应用题那么简单?”也就是说，是否存在这样的问题:验证给定答案的有效性很容易，但从头开始寻找答案却很困难?

现在我们已经直观地理解了NP是什么，我们必须挑战我们的直觉。事实证明，在某种意义上，“多项选择题”是最难的:如果一个人能找到其中一个“最难的”问题的解决方案，那么他就能找到所有NP问题的解决方案!40年前，当库克发现这一点时，完全出乎意料。这些“最难的”问题被称为np难问题。如果你找到其中一个的“应用题解答”，你就会自动找到每一个“简单多项选择题”的“应用题解答”!

最后，NP完全问题是那些同时是NP和NP难的问题。按照我们的类比，它们既“像选择题一样简单”，又“像应用题一样最难”。

我四处寻找，看到了许多冗长的解释。 这里有一个小图表，总结起来可能有用:

请注意难度是如何从上到下递增的:任何NP都可以简化为NP完全，任何NP完全都可以简化为NP困难，所有这些都需要P(多项式)时间。

如果你能在P时间内解决一个更难的问题，那就意味着你找到了如何在P时间内解决所有更简单的问题的方法(例如，证明P = NP，如果你知道如何在P时间内解决任何NP-完全问题)。

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

“是”或“否”条目说明:

同样是P的NP问题可以在P时间内解决。 ** np -难问题，也是np -完全问题，在P时间内可验证。 *** np -完全问题(所有这些都构成了NP-hard的子集)可能是。其余的NP困难则不是。

我还发现这个图非常有用，可以看到所有这些类型是如何相互对应的(请更加注意图的左半部分)。

找到一些有趣的定义:

对于这个特别的问题有很好的答案，所以没有必要写我自己的解释。所以我会试着提供关于不同类型计算复杂度的优秀资源。

对于那些认为计算复杂度只是关于P和NP的人来说，这里有关于不同计算复杂度问题的最详尽的资源。除了OP提出的问题，它还列出了大约500种不同类型的计算问题，并给出了很好的描述，还列出了描述这类问题的基础研究论文。

根据我的理解，np-hard问题并不比np-complete问题“更难”。事实上，根据定义，每个np完全问题都是:

在NP np-hard

——介绍。Cormen, Leiserson, Rivest, and Stein所著的算法(3ed)，第1069页

条件1。和2。翻译成英语:

语言L在NP中，和 每一种NP语言都是多项式时间可约化为语言L。