什么是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-Complete指的是非常具体的东西,你必须小心,否则你会弄错定义。首先,NP问题是一个是/否问题

对于答案为"是"的问题的每个实例都有多项式时间证明,即答案为"是",或者(等价地) 存在一种多项式时间算法(可能使用随机变量),如果问题实例的答案是“是”,那么它有非零概率回答“是”,如果答案是“否”,则它会在100%的时间内回答“否”。换句话说,该算法的假阴性率必须小于100%,并且没有假阳性。

问题X是np完全的,如果

X在NP中,并且 对于NP中的任何问题Y,都有一个从Y到X的“约简”:一个多项式时间算法,将Y的任何实例转换为X的实例,当且仅当X实例的答案是“是”时,Y实例的答案是“是”。

如果X是NP完全的,并且存在一个确定性的多项式时间算法,可以正确地解决X的所有实例(0%假阳性,0%假阴性),那么NP中的任何问题都可以在确定性多项式时间中解决(通过归约到X)。

So far, nobody has come up with such a deterministic polynomial-time algorithm, but nobody has proven one doesn't exist (there's a million bucks for anyone who can do either: the is the P = NP problem). That doesn't mean that you can't solve a particular instance of an NP-Complete (or NP-Hard) problem. It just means you can't have something that will work reliably on all instances of a problem the same way you could reliably sort a list of integers. You might very well be able to come up with an algorithm that will work very well on all practical instances of a NP-Hard problem.

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

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

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

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

np完全是一类问题。

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

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

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

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

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

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

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

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