什么是P问题、NP问题和NPC问题-并作摘要

总结如下：

多项式时间我们可以将时间复杂度分为两类； 第一类称为多项式级复杂度，其尺度n出现在底层，例如O(1)、O(logN)、O(N^a)等； 第二种称为非多项式级复杂度，例如 O(a^n)、O(N!) 等。我们将第一种时间复杂度称为多项式时间。

P 问题 如果可以找到可以在多项式时间内解决该问题的算法，则该问题就是 P 问题。

NP 问题 NP 问题有两种定义。 第一个定义：如果一个问题能够在多项式时间内验证一个解，那么这个问题就是一个NP问题。 第二个定义：如果一个问题的解可以在多项式时间内猜出，那么这个问题就是一个NP问题。

约简问题A可以约简为问题B，意味着问题A可以使用问题B的解来解决。一般来说，B的时间复杂度高于或等于A的时间复杂度。另外，约简是具有传递性的。 如果问题A可以简化为问题B，问题B可以简化为问题C，那么问题A必须简化为问题C。

NPC问题（NP完全问题） NPC问题定义为同时满足以下两个条件的问题。 首先，它必须是一个NP问题； 那么所有的NP问题都可以归结为它。 到了这个阶段，我们可以直观地了解到，目前NPC问题还没有有效的多项式算法，只能使用指数甚至阶乘复杂度搜索。

NP-Hard 问题 NP-Hard 问题不一定是 NP 问题，但所有 NP 问题都可以归结为 NP 问题。