computer-science - "P=NP?"是什么？为什么这是一个如此著名的问题？

Question

已关闭。这个问题是 off-topic 。目前不接受答案。

---

想要改进这个问题吗？ Update the question所以它是on-topic用于堆栈溢出。

已关闭10 年前。

社区去年审查了是否重新开放此问题，并将其关闭:

原始关闭原因未解决

Improve this question

P=NP 是否可能是整个计算机科学中最著名的问题。这是什么意思？为什么这么有趣？

哦，为了获得额外的分数，请发布该陈述的真实性或虚假性的证明。 :)

Answer 1

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

定义:

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

• 复杂性是以所需操作数量来衡量的时间，作为数据项数量的函数。

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

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

这里我们关心两种类型的 TM:确定性和非确定性。对于从磁带上读取的每个符号，确定性 TM 仅具有从每个状态的一次转换。一个非确定性 TM 可能有几个这样的转变，即。 e.它能够同时检查多种可能性。这有点像生成多个线程。不同之处在于，非确定性 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 个变量的 bool 表达式为 true。
目前在实践中，任何在非确定性 TM 上需要多项式时间的问题只能在确定性 TM 或传统计算机上以指数时间完成。
例如，解决真值分配问题的唯一方法是尝试 2^n 种可能性。