什么是np完全问题?为什么它在计算机科学中如此重要?
当前回答
np完全是一类问题。
P类由那些可以在多项式时间内解决的问题组成。例如，对于某个常数k，它们可以用O(nk)来求解，其中n是输入的大小。简单地说，您可以编写一个在合理时间内运行的程序。
NP类由那些在多项式时间内可验证的问题组成。也就是说，如果我们已知一个可能的解，那么我们可以在多项式时间内检验这个解是否正确。
一些例子是布尔可满足性(或SAT)问题，或哈密顿循环问题。在NP类中有很多已知的问题。
NP完全意味着问题至少和NP中的任何问题一样难。
它对计算机科学很重要，因为它已经证明了NP中的任何问题都可以转化为NP完备中的另一个问题。这意味着任何一个NP完全问题的解都是所有NP问题的解。
安全性中的许多算法依赖于NP困难问题没有已知解的事实。如果能找到解决方案，它肯定会对计算产生重大影响。
其他回答
np完全是一类问题。
P类由那些可以在多项式时间内解决的问题组成。例如，对于某个常数k，它们可以用O(nk)来求解，其中n是输入的大小。简单地说，您可以编写一个在合理时间内运行的程序。
NP类由那些在多项式时间内可验证的问题组成。也就是说，如果我们已知一个可能的解，那么我们可以在多项式时间内检验这个解是否正确。
一些例子是布尔可满足性(或SAT)问题，或哈密顿循环问题。在NP类中有很多已知的问题。
NP完全意味着问题至少和NP中的任何问题一样难。
它对计算机科学很重要，因为它已经证明了NP中的任何问题都可以转化为NP完备中的另一个问题。这意味着任何一个NP完全问题的解都是所有NP问题的解。
安全性中的许多算法依赖于NP困难问题没有已知解的事实。如果能找到解决方案，它肯定会对计算产生重大影响。
上面NP完全问题的定义是正确的，但我想我可能会对它们的哲学重要性进行抒情，因为还没有人解决这个问题。
几乎你遇到的所有复杂问题都是NP完全的。这门课有一些非常基础的东西，从计算上看和容易解决的问题是不同的。它们有自己的味道，而且不难辨认。这基本上意味着任何适度复杂的算法都不可能精确地解决——调度、优化、包装、覆盖等。
But not all is lost if a problem you'll encounter is NP Complete. There is a vast and very technical field where people study approximation algorithms, which will give you guarantees for being close to the solution of an NP complete problem. Some of these are incredibly strong guarantees -- for example, for 3sat, you can get a 7/8 guarantee through a really obvious algorithm. Even better, in reality, there are some very strong heuristics, which excel at giving great answers (but no guarantees!) for these problems.
请注意，两个非常著名的问题——图同构和因式分解——不知道是P或NP。
NP问题:-
NP问题是一类可以在非确定多项式时间内解决的问题。 非确定性算法分为两个阶段。 非确定性猜测阶段&&非确定性验证阶段。
Np问题的类型
NP完全 NP困难
NP完全问题:-
如果问题A具有以下两个性质，则称为NP完全问题
它属于NP类。 NP中的任何其他问题都可以在多项式时间内转化为P。
一些例子:
背包问题 子集和问题 顶点覆盖问题
老实说，维基百科可能是寻找答案的最佳场所。
如果NP = P，那么我们就可以比我们之前认为的更快地解决非常困难的问题。如果我们在P(多项式)时间内只解决了一个np -完全问题，那么它可以应用于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难的问题。
