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

Question

真的......我本周二正在进行最后一次毕业考试,这是我无法理解的事情之一.我意识到NP问题的解决方案可以在多项式时间内得到验证.但决定论与此有何关系？
如果你能解释我NP-complete和NP-hard得到他们的名字的地方,那就太棒了(我很确定我得到了他们的意思,我只是看不出他们的名字与他们的名字有什么关系是).
对不起,如果这是微不足道的,我似乎无法得到它( - :
谢谢大家!

Answer 1

P

在多项式时间内由确定性图灵机可以解决的所有问题的类别.

NP

在多项式时间内由非确定性图灵机可以解决的所有问题的类别(它们也可以在多项式时间内由确定性图灵机验证.)

NP-硬

一类问题"至少与NP中最难的问题一样难".形式上,如果有一个NP完全问题是多项式时间图灵可以减少的话,那么问题在于NP-Hard; (另外:如果它可以通过oracle机器用oracle机器在多项式时间内解决问题).这个名字的来源非常明显.

NPC

既有NP也有NP-Hard的问题.关于命名,即使维基百科也不确定为什么它被命名为它.

Answer 2

让我们从"不确定性"开始吧.确定性机器一次可以处于一种状态.我们实际上可以制作它们.非确定性机器是一种理论构造,一次可以处于多个状态.(这里有量子计算的相似之处,但对于我们这里的目的,它们会产生误导.忽视它们.)

如果我们想要使用确定性机器解决问题,我们会启动它,并通过一系列步骤来尝试找到问题.如果我们使用非确定性机器建模,它可以同时执行所有可能的一系列步骤.

我们要关注的一系列问题是决策问题:给出问题陈述,或者有解决方案.找到没有的解决方案或报告.例如,假设您有一组逻辑语句:A或非B,B或C或D,非-D或A或B,....给定任意集,您能找到所有变量的真值吗？所有陈述都是真的吗？

现在,让我们考虑P.假设我们用n表示问题的大小.大小可以是旅行商问题中的城市数量,上述问题中的逻辑陈述数量,等等.给定一定的n,问题将需要在给定系统上解决一定量的资源.现在,如果我们将资源或计算能力加倍,我们可以解决的问题大小会发生什么变化？如果问题是多项式复杂性,这意味着在P中,大小上升了一定的分数.它可能翻倍,或上升40%,或10%.相反,如果它具有指数复杂性,则大小会增加一定数量.我们通常认为P问题是可解决的和指数问题,因为问题变大无法解决,尽管这是一种简化.从非正式的角度来看,

假设我们可以在确定性机器上的多项式时间内解决问题.问题在于P.假设我们可以在非确定性机器上的多项式时间内求解它,这与能够在确定性机器上的多项式时间内验证所提出的解决方案是相同的.然后问题出在NP.这里的诀窍是我们不能制造真正的非确定性机器,因此问题在NP中的事实并不意味着解决它是切实可行的.

现在开始NP-complete.P中的所有问题都在NP中.对于NP中的问题A和B,我们可以说如果A在P中,那么B也是如此.这是通过找到将B重述为A类问题的方法来完成的.NP完全问题就是如果它在P中,NP中的每个问题都在P中.正如您可能猜到的那样,找到一种方法将每个可能的问题重述为一个特定问题并不容易,我会只是说上面的逻辑陈述问题(可满足性问题)是第一个被证明是NP完全的.之后它变得更容易,因为只需要证明如果问题C在P中,那么可满足性也是如此.

人们普遍认为,存在NP但不存在P的问题,并且最近公布了证据(可能会或可能不会证明有效).在这种情况下,NP完全程序是NP中最难的问题.

存在不适合该模具的问题.通常提出的旅行推销员问题是找到连接所有城市的最便宜的路线.这不是决策问题,我们无法直接验证任何建议的解决方案.我们可以将其重申为一个决策问题:给定成本C,是否有比C便宜的路线？这个问题是NP完全的,通过一些工作,我们可以像修改的NP完全形式一样轻松地解决原始TSP.因此,TSP是NP难的,因为它至少与NP完全问题一样难.

Answer 3

NP被称为NP(非确定多项式时间),因为NP问题可以通过非确定性图灵机在多项式时间内求解.

Answer 4

让我们从NP开始:在NP中,N代表"非确定性",P代表"多项式时间".如果你有一个非确定性图灵机可以在每个周期进行分支以并行探索可能性,那么就可以在多项式时间内解决这类问题("验证解决方案"替代定义最近变得流行,但它并不清楚什么"N"意味着).可以将非确定性机器与具有无限数量的处理器的并行计算机进行比较,并且能够fork()在每个指令处进行比较.

说问题Q是"NP-hard"意味着NP中的任何问题都可以减少到问题Q(在多项式时间内).由于问题之间的关系"可以简化为"是一种秩序关系,你可以将"NP-hard"视为"至少与所有NP问题一样难".

"NP完全"问题只是NP难以解决的NP问题之一.我想这类问题需要一个名字,但我不知道如何解释"完整"这个词的选择.

Answer 5

但决定论与此有何关系？

来自维基百科:

NP是所有决策问题的集合,其中"是" - 答案具有有效可验证的证据,证明答案确实是"是".更准确地说,这些证明必须通过确定性图灵机在多项式时间内验证

虽然不确定名字的历史.编辑:我猜对了.以下是猜测,但我不认为这是不合理的.

NP-Hard是任何问题,至少与NP中最难的问题一样难.因此,可以说所讨论的问题具有NP硬度,因此NP-Hard.

如果可以快速解决NP-complete中的任何单个问题,那么NP中的每个问题也可以快速解决.因此,可以解决整套NP问题.

EDIT2:维基百科的完整(复杂性)文章指出:

如果复杂性类在复杂性类中是"最难"或"最具表现力"的问题之一,那么复杂性类的计算问题是完整的