什么是“P=NP?”，为什么这是一个如此著名的问题?

就我所知做一个简短的总结:

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

其他的问题，比如找到一条穿过图中每个顶点的路径，或者从公钥中获取RSA私钥就更难了(O(e^n))。

但是CS语言告诉我们，问题在于我们不能将非确定性图灵机“转换”为确定性图灵机，然而，我们可以将非确定性有限自动机(如正则表达式解析器)转换为确定性自动机(好吧，你可以，但机器的运行时间会很长)。也就是说，我们必须尝试每一条可能的路径(通常聪明的计算机教授会排除一些)。

这很有趣，因为甚至没有人知道答案。有人说这是真的，有人说这是假的，但没有共识。另一件有趣的事情是，解决方案对公钥/私钥加密(如RSA)是有害的。你可以像现在生成RSA密钥一样轻易地破解它们。

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

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

定义:

• 多项式时间意味着算法的复杂度是O(n^k)，其中n是数据的大小(例如列表中要排序的元素的数量)，k是一个常数。

• 复杂度是用它所需要的操作数量来衡量的时间，作为数据项数量的函数。

• Operation是任何对特定任务有意义的基本操作。对于排序，基本操作是比较。矩阵乘法的基本运算是两个数的乘法。

现在的问题是，确定性和非确定性是什么意思?有一种抽象的计算模型，一种被称为图灵机(TM)的虚构计算机。这台机器有有限数量的状态，还有一个无限的磁带，它有离散的单元，可以写入和读取有限的一组符号。在任何给定的时间，TM都处于它的一种状态，它正在查看磁带上的一个特定单元格。根据它从单元格中读取的内容，它可以将新符号写入该单元格，将磁带向前或向后移动一个单元格，并进入不同的状态。这叫做状态转换。令人惊讶的是，通过仔细构造状态和转换，您可以设计一个TM，它相当于任何可以编写的计算机程序。这就是为什么它被用作一个理论模型来证明计算机能做什么和不能做什么。

这里有两种TM:确定性的和非确定性的。对于从磁带中读取的每个符号，确定性TM只有从每个状态到每个状态的一次转换。一个非确定性TM可以有几个这样的转换，即它可以同时检查几个可能性。这有点像生成多个线程。不同之处在于，非确定性TM可以生成任意数量的这样的“线程”，而在真正的计算机上，一次只能执行特定数量的线程(等于cpu数量)。实际上，计算机基本上是带有有限磁带的确定性TMs。另一方面，非确定性TM无法在物理上实现，除非使用量子计算机。

事实证明，任何可以用非确定性TM解决的问题都可以用确定性TM解决。然而，尚不清楚这需要多长时间。陈述P=NP意味着如果一个问题在非确定性TM上花费多项式时间，那么人们可以构建一个确定性TM，它也可以在多项式时间内解决相同的问题。到目前为止，还没有人能够证明这是可以做到的，但也没有人能够证明这是不能做到的。

NP完全问题是指一个NP问题X，这样任何NP问题Y都可以通过多项式约简化为X。这意味着，如果有人提出了一个NP完全问题的多项式时间解，那也会给出任何NP问题的多项式时间解。这样就证明了P=NP。相反，如果有人能证明P!=NP，那么我们可以肯定，在传统计算机上没有办法在多项式时间内解决NP问题。

对于P=的“什么”和“为什么”，我没有什么可以补充的了。NP部分的问题，但是关于证明。不仅证明值一些额外的学分，但它将解决一个年问题。最近进行了一项有趣的民意调查，关于证明的主题，公布结果(PDF)绝对值得一读。

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

假设我们有一个问题，需要一定数量的输入，并且有各种潜在的解决方案，这些解决方案可能解决也可能解决不了给定输入的问题。益智杂志中的逻辑谜题就是一个很好的例子:输入是条件(“乔治不住在蓝色或绿色的房子里”)，潜在的解决方案是一组语句(“乔治住在黄色的房子里，种豌豆，养狗”)。一个著名的例子是旅行推销员问题:给定一个城市列表，从一个城市到另一个城市的时间，以及一个时间限制，一个潜在的解决方案是一个城市列表，按照推销员访问它们的顺序排列，如果旅行时间的总和小于时间限制，它就会起作用。

如果我们能有效地检查一个潜在的解决方案，看看它是否有效，这样的问题就属于NP。例如，给定一个销售人员要按顺序访问的城市列表，我们可以将每个城市之间的旅行时间加起来，并很容易地查看它是否在时间限制之内。如果我们能有效地找到解决方案，那么问题就在P中。

(高效，在这里有一个精确的数学意义。实际上，这意味着解决大问题并不是不合理的困难。当搜索一个可能的解决方案时，低效的方法是列出所有可能的潜在解决方案，而有效的方法需要搜索一个更有限的集合。)

因此，P=NP问题可以这样表达:如果你能有效地验证上述问题的解决方案，你能有效地找到解决方案(或证明没有解决方案)吗?最明显的答案是“为什么你应该能够?”，这就是今天的问题所在。没有人能够以这样或那样的方式证明它，这困扰着许多数学家和计算机科学家。这就是为什么任何能证明解决方案的人都可以从克雷普基金会获得一百万美元。

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

你可能听过NP-complete这个描述。一个NP完全问题是一个NP问题(当然)，并且有一个有趣的性质:如果它在P中，那么每个NP问题都是，因此P=NP。如果你能找到一种有效解决旅行推销员问题或益智杂志上的逻辑谜题的方法，你就可以有效地解决NP中的任何问题。NP完全问题在某种程度上是NP问题中最难的一类。

所以，如果你能找到任何np完全问题的有效通解技术，或者证明不存在这样的问题，名利就是你的了。

1. 如果答案可以在多项式时间内计算，则在P (__abco0olynomial time)中存在一个是或否的问题。
2. 一个是或否的问题是在NP (__abc1 -deterministic __abc2polynomial time)，如果一个是答案可以在多项式时间内是验证。

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

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

有大量已知的重要问题是NP完整的(基本上，如果任何这些问题被证明是在P中，那么所有 NP问题被证明是在P中)。如果P = NP，那么所有这些问题都将被证明有一个有效的(多项式时间)解。

大多数科学家认为P!=NP。然而，还没有证据证明P =NP或P!=NP。如果有人为任何一个猜想提供了证明，他们将赢得100万美元。

首先，一些定义:

• 如果你可以在小于n^k的时间内为某些k计算出一个解决方案，则特定问题属于P，其中n是输入的大小。例如，排序可以在小于n^2的n log n中完成，因此排序是多项式时间。

• 如果存在一个k，使得存在一个最大为n^k的解，并且你可以及时验证最大为n^k，则问题属于NP。以图的3-着色为例:给定一个图，3-着色是一个大小为O(n)的(顶点，颜色)对的列表，你可以及时验证O(m)(或O(n^2))是否所有相邻的都有不同的颜色。因此，只有在有一个简短且易于验证的解决方案的情况下，一个图才可以是3色的。

NP的等效定义是“可以用__abc确定性图灵机在__abc 1多项式时间内解决的问题”。虽然这告诉你这个名字的来源，但它并没有让你对NP问题有同样直观的感觉。

注意P是NP的一个子集:如果你能在多项式时间内找到一个解，那么就有一个解可以在多项式时间内被验证——只要检查给定的解是否等于你能找到的解。

为什么P =? NP这个问题很有趣?要回答这个问题，首先需要了解什么是np完全问题。简单地说,

• 如果(1)L在P中，且(2)解决L的算法可以用于解决NP中的任何L'问题，则问题L是NP完备的;也就是说，给定L'的一个实例，你可以创建一个L的实例，当且仅当L'的实例有解时，它有解。从形式上讲，NP中的每个问题L'都是可约到L。

注意，L的实例必须是多项式时间可计算的，并且具有多项式大小，大小为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)。也就是说,

< p > not ((u_h and not u_l) and (v_h and not v_l) or ...) 列举所有相等的构型，并规定它们都不是情况

__abc0 '将所有这些约束放在一起给出一个具有多项式大小的布尔公式(O(n+m))。你可以检查它需要多项式的时间来计算:你在每个顶点和每条边做直接的O(1)的东西。

如果你能解出我所做的布尔公式，那么你也可以解出图的着色:对于每一对变量v_h和v_l，让v的颜色与这些变量的值相匹配。根据公式的构造，相邻的颜色不会相等。

因此，如果图的3色是np完备的，那么布尔公式可满足性也是np完备的。

我们知道图的3色是np完备的;然而，历史上我们已经知道，通过首先展示布尔电路可满足性的np完整性，然后将其减少到3-着色性(而不是相反)。