代码之家 › 专栏 › 技术社区 › Oren A

为什么NP问题被这样称呼(NP-hard和NP-complete)?

p-np complexity-theory computer-science

Oren A · 技术社区 · 14 年前

真正地。。这个星期二我要参加毕业典礼的最后一次考试,这是我永远无法理解的事情之一。我意识到NP问题的解可以在多项式时间内得到验证。但决定论与此有什么关系呢?
如果你能解释一下NP-complete和NP-hard的名字是从哪里来的,那就太好了(我很确定我理解它们的意思了,我只是不知道它们的名字和它们是什么有什么关系)。
抱歉,如果这是琐碎的,我只是不能得到它(-:
谢谢大家!

5 回复 | 直到 14 年前

Yuval Adam 14 年前

第

一类可以由一个

NP

一类可以由一个 不确定性 多项式时间内的图灵机(也可以通过

计算复杂性

NPC公司

既有NP难又有NP难的一类问题。关于命名, even wikipedia

David Thornley 14 年前

让我们从“不确定性”开始。确定性机器一次可以处于一种状态。我们真的可以做。不确定性机器是一种理论结构,一次可以处于多个状态。(这里与量子计算有相似之处,但就我们的目的而言,它们是误导性的。别理他们。)

如果我们想用确定性机器来解决一个问题,我们启动它,它会经过一系列的步骤来试图找到一个问题。如果我们使用不确定性机器建模,它可以同时经历所有可能的一系列步骤。

我们将要关注的一组问题是决策问题:给定一个问题陈述,要么有解决方案要么没有。找到一个解决方案或报告没有。例如,假设您有一组逻辑语句:a或not-B,B或C或D,not-D或a或B。。。。给定一个任意的集合,你能找到所有变量的真值吗,这样所有的语句都是真的?

假设我们可以在确定的机器上用多项式时间来解决这个问题。问题在P中,假设我们可以在不确定机器上用多项式时间求解,这与在确定机器上用多项式时间验证所提出的解是一样的。那么这个问题就是NP问题。这里的诀窍是我们不能制造出真正的不确定性机器,所以问题在NP中并不意味着它是可以解决的。

现在开始NP完全。P中的所有问题都是NP。对于NP中的问题A和B,我们可以说,如果A在P中,B也在P中。这是通过找到一种方法,将B重新表述为A类问题来实现的。一个NP完全问题是这样的,如果它在P中,NP中的每一个问题都在P中。正如你可能猜到的,找到一种方法来重述每一个可能的问题作为一个特定的问题是不容易的,我只想说,上面有逻辑陈述的问题(可满足性问题)是第一个被证明的NP完全问题。在那之后就容易多了,因为只要证明问题C在P中,可满足性也在P中。

sepp2k 14 年前

NP被称为NP(nondeterministicpolymonarytime),因为一个NP问题可以在多项式时间内用不确定图灵机求解。

Billy ONeal IS4 14 年前

让我们从NP开始:在NP中,N表示“不确定性”,P表示“多项式时间”。如果你有一个不确定的图灵机,它可以在每个周期分支,并行地探索各种可能性,那么这类问题就可以在多项式时间内得到解决(“验证解决方案”的替代定义最近很流行,但它没有明确“N”是什么意思)。不确定性机器可以比作拥有无限多个处理器的并行计算机,并且具有 fork() 每一个指令。

如果说问题Q是NP难的,那么NP中的任何问题都可以归结为问题Q(在多项式时间内)。由于问题之间的“可化为”关系是一种序关系,你可以把“NP-hard”看作“至少和所有NP问题一样难”的意思。

Billy ONeal IS4 14 年前

从 Wikipedia

NP是所有决策问题的集合,对于这些决策问题,“是”的答案有效地证明了答案确实是“是”的事实。更准确地说,这些证明必须在多项式时间内由 确定性 图灵机

NP-Hard是任何至少和NP中最难的问题一样难的问题。因此,可以说这个问题是NP难的,因此是NP难的。

如果NP完全中的任何一个问题都能快速求解,那么NP完全中的每一个问题都能快速求解。因此,这套完整的NP问题是可以解决的。

编辑2 : Wikipedia's Complete (Complexity) 文章指出: