老实说，维基百科可能是寻找答案的最佳场所。

如果NP = P，那么我们就可以比我们之前认为的更快地解决非常困难的问题。如果我们在P(多项式)时间内只解决了一个np -完全问题，那么它可以应用于np -完全范畴内的所有其他问题。

NP代表非确定性多项式时间。

这意味着使用非确定性图灵机(就像常规图灵机，但也包括非确定性“选择”函数)可以在多项式时间内解决问题。基本上，解必须在多边形时间内可测试。如果是这样的话，一个已知的NP问题可以用修改输入的给定问题来解决(一个NP问题可以简化为给定问题)，那么这个问题就是NP完全的。

从np完全问题中得到的主要东西是，它不能以任何已知的方式在多项式时间内解决。NP-Hard/NP-Complete是一种表明某些类型的问题在现实时间内无法解决的方法。

编辑:正如其他人所注意到的，np完全问题通常有近似解。在这种情况下，近似解通常给出一个近似界，用特殊的符号告诉我们这个近似有多接近。

基本上这个世界的问题可以分为

1)无法解决的问题 2)棘手问题 3) np问题 4) P-Problem

1)第一个是没有解决问题的办法。 2)其次是需要指数时间(即O (2 ^ n)以上)。 3)第三个是NP。 4)第四个问题很简单。

P:多项式时间问题的解。

NP:指多项式时间尚未找到一个解决方案。我们不确定有没有多项式时间的解决方案，但一旦你提供了一个解决方案，这个解决方案可以在多项式时间验证。

NP完全:是指在多项式时间中我们还没有找到一个解，但它可以在多项式时间中得到验证。NP中的NPC问题是比较困难的问题，所以如果我们能证明NPC问题有P个解，那么NP问题就能在P个解中找到。

NP困难:指多项式时间尚未找到解决方案，但它肯定无法在多项式时间内得到验证。NP难的问题超过NPC难的问题。

np完全是一类问题。

P类由那些可以在多项式时间内解决的问题组成。例如，对于某个常数k，它们可以用O(nk)来求解，其中n是输入的大小。简单地说，您可以编写一个在合理时间内运行的程序。

NP类由那些在多项式时间内可验证的问题组成。也就是说，如果我们已知一个可能的解，那么我们可以在多项式时间内检验这个解是否正确。

一些例子是布尔可满足性(或SAT)问题，或哈密顿循环问题。在NP类中有很多已知的问题。

NP完全意味着问题至少和NP中的任何问题一样难。

它对计算机科学很重要，因为它已经证明了NP中的任何问题都可以转化为NP完备中的另一个问题。这意味着任何一个NP完全问题的解都是所有NP问题的解。

安全性中的许多算法依赖于NP困难问题没有已知解的事实。如果能找到解决方案，它肯定会对计算产生重大影响。

这是一类问题，我们必须模拟每一种可能性，以确保我们有最优解。

对于一些np完全问题，有很多好的启发式方法，但它们充其量只是一个有根据的猜测。

NP问题:-

NP问题是一类可以在非确定多项式时间内解决的问题。 非确定性算法分为两个阶段。 非确定性猜测阶段&&非确定性验证阶段。

Np问题的类型

NP完全 NP困难

NP完全问题:-

如果问题A具有以下两个性质，则称为NP完全问题

它属于NP类。 NP中的任何其他问题都可以在多项式时间内转化为P。

一些例子:

背包问题 子集和问题 顶点覆盖问题