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

Question

<分区>

Answer 1

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

定义:

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

• 复杂性是用时间来衡量的，作为数据项数量的函数，它需要执行多少操作。

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

现在的问题是，确定性与非确定性是什么意思？有一个抽象的计算模型，称为图灵机 (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 表达式为真。
目前在实践中，任何在非确定性 TM 上需要多项式时间的问题只能在确定性 TM 或传统计算机上以指数时间完成。
例如，解决真值分配问题的唯一方法是尝试 2^n 种可能性。