什么是“P = NP？”，为什么这是一个着名的问题？
P = NP是否可能是所有计算机科学中最有名的问题。 这是什么意思？ 为什么它很有趣？
哦，为了获得额外的信用，请发表声明的真实或虚假证明。 :)
P代表多项式时间。 NP代表非确定性多项式时间。
定义：
多项式时间意味着算法的复杂度为O（n ^ k），其中n是数据的大小（例如，要排序的列表中的元素的数量），并且k是常数。
作为数据项数量的函数， 复杂性是根据所需操作的数量来衡量的。
作为特定任务的基本操作， 操作是有意义的。 对于排序的基本操作是一个比较。 对于矩阵乘法，基本操作是两个数字的乘法。
现在的问题是，确定性与非确定性意味着什么。 有一个抽象的计算模型，一个称为图灵机（TM）的虚拟计算机。 这台机器的状态数量是有限的，还有一个无限大的磁带，它具有离散的单元，其中可以写入和读取一组有限的符号。 TM在任何时候都处于其状态之一，并且正在看磁带上的特定单元。 根据从该单元读取的内容，它可以在该单元中写入新的符号，将磁带向前或向后移动一个单元，并进入不同的状态。 这被称为状态转换。 令人惊讶的是，通过仔细构建状态和转换，您可以设计一个TM，它等价于任何可以编写的计算机程序。 这就是为什么它被用作证明计算机可以做什么和不可以做什么的理论模型。
在这里有两种关注我们的TM：确定性和非确定性。 确定性TM仅对每个符号从每个状态进行一次转换，它从磁带上读取。 一个非确定性的TM可能有几个这样的转换，即它能够同时检查几种可能性。 这就像产生多个线程一样。 区别在于非确定性TM可以产生尽可能多的这样的“线程”，而在真实计算机上，一次只能执行特定数量的线程（等于CPU的数量）。 实际上，计算机基本上是具有有限磁带的确定性TM。 另一方面，除了可能用量子计算机以外，一个非确定性TM不能被物理地实现。
已经证明，任何可以通过非确定性TM解决的问题都可以通过确定性TM来解决。 但是，目前尚不清楚需要多少时间。 语句P = NP意味着如果一个问题在非确定性TM上需要多项式时间，那么可以建立一个确定性的TM，它也将在多项式时间内解决相同的问题。 到目前为止，没有人能够证明它可以完成，但没有人能够证明它不能完成。
NP完全问题意味着一个NP问题X，这样任何NP问题Y都可以通过多项式约化减少到X. 这意味着如果有人想出一个NP完全问题的多项式时间解，那么也将给出任何NP问题的多项式时间解。 因此，这将证明P = NP。 相反，如果有人要证明P！= NP，那么我们可以确定在常规计算机上没有办法在多项式时间内解决NP问题。
NP完全问题的一个例子是找到一个真值分配的问题，它会使包含n个变量的布尔表达式为真。
目前在实践中，任何在非确定性TM上花费多项式时间的问题只能在确定性TM或常规计算机上以指数时间完成。
例如，解决真值分配问题的唯一方法是尝试2 ^ n个可能性。
直觉上，我们可以看到，如果问题出现在P中 ，那么它就在NP中 。 给出P中潜在的问题答案，我们可以通过简单地重新计算答案来验证答案。
不太明显，而且更难回答的是NP中的所有问题是否都在P中 。 我们可以在多项式时间内验证答案的事实是否意味着我们可以在多项式时间内计算答案？
有许多重要问题已知是NP完全的 （基本上，如果任何这些问题都证明在P中 ，那么所有的NP问题都被证明在P中 ）。 如果P = NP ，那么所有这些问题将被证明具有有效的（多项式时间）解决方案。
大多数科学家认为P ！= NP 。 然而，对于P = NP或P ！= NP还没有证据。 如果有人提供任何猜想的证据，他们将赢得100万美元。
为了给出我能想到的最简单的答案：
假设我们有一个需要一定数量输入的问题，并且有各种可能的解决方案，这些解决方案可能解决或不解决给定输入的问题。 益智杂志中的逻辑难题就是一个很好的例子：投入是条件（“乔治不住在蓝色或绿色的房子里”），潜在的解决方案是一个陈述清单（“乔治住在黄色房子，生长豌豆，并拥有狗“）。 一个着名的例子是旅行推销员问题：给出一个城市列表，以及从任何城市到其他任何城市的时间和时间限制，潜在的解决方案将是推销员访问它们时的城市列表，以及如果旅行时间的总和小于时间限制，它就会起作用。
如果我们能够有效地检查潜在的解决方案，看看它是否有效，那么这个问题就在NP中。 例如，给定推销员按顺序访问的城市列表，我们可以将城市之间的每次旅行的时间加起来，并且容易地看到它是否在时间限制之内。 如果我们能够有效地找到解决方案，那么问题在于P。
（有效地，这里有一个精确的数学意义，实际上，这意味着大问题不是不合理地难以解决的，当寻找可能的解决方案时，一种低效的方法是列出所有可能的解决方案或者接近，而有效的方法则需要搜索更有限的集合。）
因此，P = NP问题可以用这种方式表达：如果您可以有效地验证上述问题的解决方案，您是否可以有效地找到解决方案（或者证明没有解决方案）？ 显而易见的答案是“为什么你应该能够？”，而这正是今天问题所在。 没有人能够以这种或那种方式证明它，并且困扰了很多数学家和计算机科学家。 这就是为什么任何能够证明解决方案的人都能从Claypool基金会获得一百万美元的收益。
我们通常假设P不等于NP，没有找到解决方案的一般方法。 如果事实证明P = NP，许多事情都会改变。 例如，密码学将变得不可能，并且在互联网上具有任何类型的隐私或可验证性。 毕竟，我们可以有效地把加密的文本和密钥生成原始文本，所以如果P = NP，我们可以在事先不知道它的情况下有效地找到密钥。 密码破解将变得微不足道。 另一方面，我们可以有效地解决所有类型的计划问题和资源分配问题。
您可能已经听说过NP-complete的说明。 一个NP完全问题是一个NP（当然），并且具有这个有趣的性质：如果它在P中，每个NP问题都是，那么P = NP。 如果你能找到一种有效解决旅行推销员问题的方法，或者解谜杂志中的逻辑谜题，你可以有效地解决NP中的任何问题。 一个NP完全问题在某种程度上是NP问题中最难解决的问题。
所以，如果你能为任何NP完全问题找到一个有效的通用解决方案，或者证明没有这样的解决方法，那么名利就是你的。
链接地址: http://www.djcxy.com/p/39993.html上一篇: What's "P=NP?", and why is it such a famous question?
下一篇: If a NP solved in polynomial time, can Satisfiability solved in polynomial time