为什么NP方式会这样叫（和NP
真的..我本周二正在接受最后一次毕业考试，这是我永远无法理解的事情之一。 我意识到NP问题的解决方案可以在多项式时间内得到满足。 但决定论与此有什么关系？
如果你能向我解释NP-complete和NP-hard在哪里取得他们的名字，那就太棒了（我很确定我明白了他们的意思，我只是不知道他们的名字与他们的名字有什么关系是）。
对不起，如果这是微不足道的，我似乎无法得到它（ - ：
谢谢大家！
P
在多项式时间内可以通过确定性图灵机解决的所有问题的类。
NP
在多项式时间内可由非确定性图灵机解决的所有问题的类别（它们也可在多项式时间内由确定性图灵机验证）。
NP-硬
一类问题“至少与NP中最困难的问题一样困难”。 形式上，如果存在一个多项式时间Turing可还原的NP完全问题，则NP-Hard存在问题; （还有：如果它可以用一个oracle机器在多项式时间内用问题的oracle解决）。 这名字来自哪里非常明显。
NPC
既是NP也是NP-Hard的一类问题。 关于命名，甚至维基百科也不确定它为什么被命名。
我们从“不确定性”开始。 确定性机器可以一次处于一种状态。 我们实际上可以制造它们。 非确定性机器是一种理论构造，可以同时处于多个状态。 （这里和量子计算有相似之处，但在我们这里他们误导他人，忽视他们。）
如果我们想用一个确定性机器来解决问题，那么我们启动它，然后通过一系列步骤来尝试找出问题。 如果我们使用非确定性机器进行建模，它可以同时经历所有可能的一系列步骤。
我们要关心的一系列问题是决策问题：给出问题陈述，或者有解决方案。 找到解决方案或报告没有。 例如，假设您有一组逻辑语句：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作为一种问题来完成的。 一个NP完全问题就是这样的一个问题，如果它在P中，NP中的每个问题都在P中。正如你可能猜到的那样，找到一种方法来将每个可能的问题重新表达为一个特定的问题并不容易，我会只要说上面的逻辑陈述问题（可满足性问题）是第一个被证明的NP完全问题。 之后，它变得更加容易，因为只需要证明如果问题C在P中，那么可满足性也是如此。
一般认为NP存在问题而不是P，最近发表了一个证明（这可能或可能不是有效的）。 在这种情况下，NP完全程序是NP中最难解决的问题。
有些问题不适合这种模具。 正常情况下，旅行推销员问题是找到连接所有城市的最便宜的路线。 这不是一个决策问题，我们无法直接验证任何提议的解决方案。 我们可以将其重述为一个决策问题：给定成本C，是否存在比C更便宜的路线？ 这个问题是NP完全的，通过一些工作，我们可以像修改的NP完全形式一样容易地解决原始TSP。 因此，TSP是NP难的，因为它至少与NP完全问题一样困难。
NP称为NP（非确定性多项式时间），因为NP问题可以由非确定性的图灵机在多项式时间内求解。
链接地址: http://www.djcxy.com/p/39969.html