什么是"P=NP?", 为什么是这样一个着名的问题吗？[关闭]

Question

该问题是否P=NP也许是最有名的所有计算机科学。这是什么意思？为什么这么有趣?

哦，对额外的信贷，请发的证明的声明的真相或谎言。:)

Answer 1

P代表的多项式的时间。NP代表不确定的多项式的时间。

定义：

• 时间多项式 意味着复杂的算法是O(n^k)，其中n大小的数据(e。g。数量元素的列表中用于进行排序)，并k是一个恒定不变。

• 复杂性 是时测定数量的操作它将采取，作为一功能的数据项目。

• 操作 是什么意义作为一种基本的操作为一项特殊任务。对于排序的基本操作一比较。为矩阵乘基本操作是乘两个数字。

现在的问题是，什么不确定性与不确定的意思。那是一个抽象计算模型，一个虚构的计算机呼叫图灵机(TM)。这台机器有有限数量的国家和一个无限的磁带，其中有离散的细胞进入这一组有限的符号可以写和阅读。在任何给定的时间，TM是其中一个国家，这是在寻找一个特定的细胞上的磁带。根据什么它会读取从那个细胞就可以写一个新的象征入该小区，移动磁带一个细胞进或落后，并进入一个不同的状态。这就是所谓的状态过渡。令人惊讶的是，通过仔细建设国家和过渡，可以设计一个TM，这是等同于任何计算机程序，可以编写的。这就是为什么它被用作一种理论模型，用于证明的事情有什么计算机可以和不可以做。

有两种类型的TM的关切，我们在这里:的确定性和不确定性的。的确定性TM只有一个过渡，从每个国家的每个符号，这是读了磁带。一个不确定的TM可能有几个这样的过渡，i。e.它是能够检查的几种可能性的同时进行。这是那种喜欢产卵多线程。不同的是，非确定性TM可以产生许多这样的"线"，因为它希望，而上一个真正的计算机仅有一特定数目的线可以执行的时间(相等数量的Cpu).在现实中，计算机基本上都是确定运用有限的磁带。另一方面，一个不确定的TM无法实际实现，也许除了与量子计算机。

它已经证明，任何问题是可以解决的一个不确定的TM是可以解决的确定性。然而，不清楚有多少时间，它将采取。发言P=NP意味着，如果一个问题需要时间多项式上的不确定性TM，然后可以建立一个确定性的TM这将解决同样的问题还在多项式的时间。迄今为止没有人已经能够表明，它是可以做到的，但没有人能够证明它不能做，要么。

NP-完整的问题意味着NP问题，这样，任何NP问题Y可以减少X通过多项式减少。这意味着，如果任何人都配备了多项式时解决一个NP-完整的问题，这也将得到多项式的时间解决任何NP问题。因此，将证明，P=NP。相反，如果有人证明P!=NP，然后我们可以肯定，有没有办法解决NP问题在多项式的时间在一个传统的电脑。

一个例子NP-完整的问题是问题找到一个事实分配，这将使布尔表达的含n变量真实的。
目前在实践中的任何问题，需要时间多项式上的不确定性TM只能在指数时间上的确定性TM或在一个传统的电脑。
例如，只有这样，才能解决的事实分配的问题是试图2^正的可能性。

Answer 2

1. 如果可以在多项式时间内计算答案，则 P （ P oulinomial time）中的是或否问题。
2. 如果答案是肯定的，则 NP （ N 确定性 P oulinomial时间）是或否的问题< em>在多项式时间内验证。

直观地，我们可以看到，如果问题出在 P ，那么它在 NP 中。鉴于 P 中问题的潜在答案，我们可以通过简单地重新计算答案来验证答案。

不太明显，更难以回答的是， NP 中的所有问题是否都在 P 。我们能在多项式时间内验证答案的事实是否意味着我们可以在多项式时间内计算答案？

已知有大量重要问题 NP - 完成（基本上，如果这些问题被证明属于 P ，那么所有 NP 问题都证明在 P 中。如果 P = NP ，则所有这些问题都将被证明具有有效（多项式时间）解决方案。

大多数科学家认为 P ！= NP 。但是，尚未确定 P = NP 或 P ！= NP 的证据。如果有人提供任何猜想的证据，他们将赢得100万美元。

Answer 3

给出我能想到的最简单的答案：

假设我们遇到一个需要一定数量输入的问题，并且有各种可能的解决方案，这些解决方案可能会或可能不会解决给定输入的问题。拼图杂志中的逻辑谜题将是一个很好的例子：输入是条件（“乔治不住在蓝色或温室里”），潜在的解决方案是一系列陈述（“乔治生活在黄屋，种豌豆，并拥有狗“）。一个着名的例子是旅行商问题：给出一个城市列表，从任何城市到任何其他城市的时间和时间限制，潜在的解决方案将是销售人员访问它们的顺序的城市列表，以及如果旅行时间的总和小于时间限制，它将起作用。

如果我们能够有效地检查潜在的解决方案以确定它是否有效，那么这个问题就出现在NP中。例如，给定销售员按顺序访问的城市列表，我们可以将城市之间每次旅行的时间相加，并轻松查看是否在时间限制之内。如果我们能够有效地找到解决方案，那么问题在于P。

（有效地，这里具有精确的数学意义。实际上，这意味着大问题并非难以解决。在寻找可能的解决方案时，一种低效的方法是列出所有可能的潜在解决方案，或者某些东西接近这一点，虽然一种有效的方法需要搜索更有限的集合。）

因此，P = NP问题可以这样表达：如果您能够有效地验证上述排序问题的解决方案，您能找到有效的解决方案（或证明没有）吗？显而易见的答案是“你为什么能够这样做？”，这就是今天的问题所在。没有人能够以某种方式证明这一点，这困扰了许多数学家和计算机科学家。这就是为什么任何能够证明这个解决方案的人都能从Claypool基金会获得一百万美元。

我们通常假设P不等于NP，没有找到解决方案的一般方法。如果事实证明P = NP，很多事情都会发生变化。例如，密码学将变得不可能，并且在互联网上具有任何形式的隐私或可验证性。毕竟，我们可以有效地获取加密文本和密钥并生成原始文本，因此如果P = NP，我们可以在不事先知道的情况下有效地找到密钥。密码破解将变得微不足道。另一方面，我们可以有效地解决各类规划问题和资源分配问题。

您可能听说过NP-complete的描述。 NP完全问题是NP（当然），并且具有这个有趣的特性：如果它在P中，则每个NP问题都是，因此P = NP。如果你能找到一种有效解决旅行商问题的方法，或者从拼图杂志中找到逻辑难题，你就可以有效地解决NP中的任何问题。在某种程度上，NP完全问题是最难解决的NP问题。

所以，如果你能找到一个有效的通用解决方案技术来解决任何NP完全问题，或者证明不存在这样的问题，那么名誉和财富都属于你。

Answer 4

来自我谦虚知识的简短摘要：

有一些简单的计算问题（比如找到图中两点之间的最短路径），可以非常快速地计算出来（O（n ^ k），其中n是输入的大小，k是常数（在图形的情况下，它是顶点或边的数量））。

其他问题，比如找到跨越图中每个顶点的路径或从公钥获取RSA私钥更难（O（e ^ n））。

但CS说话的问题在于我们无法将非确定性图灵机“转换”为确定性机器，但我们可以将非确定性有限自动机（如正则表达式解析器）转换为确定性机器人（好吧，你可以，但机器的运行时间将花费很长时间）。也就是说，我们必须尝试所有可能的路径（通常聪明的CS教授可以排除一些）。

这很有趣，因为没有人对解决方案有任何想法。有人说这是真的，有人说这是假的，但没有达成共识。另一个有趣的事情是，解决方案对公钥/私钥加密（如RSA）有害。您可以像现在生成RSA密钥一样轻松破解它们。

这是一个非常鼓舞人心的问题。

Answer 5

对于问题的P =？NP部分，我可以添加的内容并不多，但是在证明方面。一个证明不仅值得一些额外的功劳，而且它将解决其中一个千年问题。最近进行了一项有趣的民意调查，公布的结果（PDF）关于证明的主题，绝对值得一读。

Answer 6

首先，一些定义：

• 一个特别的问题是在P如果可以计算出一个解决方案的时间不到 n^k 对于一些 k, ，哪里 n 是的尺寸的输入。例如，分类可以做到 n log n 这是不到 n^2, ，这样分类是多项式的时间。

• 一个问题是在NP如果存在 k 如存在着一个解决方案的大小，在大多数 n^k 你可以验证的时间至多 n^k.需要3-色的图表：给出一个曲线图3-色列(顶点，彩色)对其拥有的大小 O(n) 你可以验证时间 O(m) (或 O(n^2))是否所有的邻居有不同的颜色。因此，一个图表3-貌似只有当有一个简短和易于核实的解决方案。

一个同等定义的NP是"可以解决的问题通过一个 Nondeterministic图灵机的 Polynomial时间"。同时，告诉你名字的来源，它不会给你同样的直观的感觉是什么NP问题等。

注意到P的一个子集NP：如果你能找到一个解决方案在多项式时，有一个解决方案，它可以核实的时间多项式--只是检查，给出解决方案等于对一个您可以找到。

为什么是问题 P =? NP 有趣吗?要回答这个问题，一个首先需要看看有什么NP-完整的问题。简单地说，

• 问题L NP-完整的，如果(1)升是在P，和(2)一种算法，它解决了我可以用来解决任何问题L'在NP;就是说，给出实例L'你可以创建的一个实例，我有一个解决方案，如果并且只有当实例的L'具有一个解决方案。从形式上来说，每一个问题L'在NP 可还原 到洛杉

注意的实例，我必须多项时可计算的，并有多项大小，大小L';这种方式，解决NP-完整的问题在多项式的时间为我们提供了一个时间多项式解决 所有 NP问题。

这里有一个例子：假设我们知道，3-色的图表是一个NP-困难的问题。我们要证明，决定可满足性的布尔公式是一个NP-困难的问题。

每个顶点v，有两个布变量v_h和v_l，并要求(v_h或v_l):每一对可以仅有的价值{01,10,11}我们可以认为以色1、2和3。

每个边缘(u,v)，有的要求(u_h,u_l)!= (v_h,v_l).就是

not ((u_h and not u_l) and (v_h and not v_l) or ...) 列举所有的平等配置和规定他们都不是这种情况。

AND'ing在一起的所有这些限制给布尔公式，它具有多项式的大小(O(n+m)).你可以检查，这需要时间多项式计算：你在做简单 O(1) 东西每顶点和每边缘。

如果你可以解决布尔公式我做了，然后你也可以解决形图颜色，对每个变量v_h和v_l，我们的颜色v是一个匹配的价值观的这些变量。通过建设式，邻居不会有平等的颜色。

因此，如果3-色的图表是NP-完成，因此是布尔-公式可满足性.

我们知道，3-色的图表是NP-完整；然而，从历史上看，我们都知道，通过第一次表示NP-完整性的布尔-路-可满足性，然后再减少到3-着色性(而不是周围的其他方法).