134
个编辑
更改
跳到导航
跳到搜索
小第481行：
第481行： + + + + + + + + + + + + + + + + + + + + + + 第488行：
第510行： + + + 第507行：
第532行： + + + + + + + 第579行：
第611行： − + − 任何一个NP完全问题的算法都不是多项式时间复杂度。+ + + + + + + + + + + + + + + + + + + + + + + + + + + +
组织了一下整体结构
这些障碍也导致一些计算机科学家提出，P/NP问题可能独立于标准公理系统，如 ZFC (无法在其中被证明或否定)。对独立性结果的解释可以是对任何 np 完全问题都不存在多项式时间算法，这样的证明不能在(例如)中构造在 ZFC 中，np- 完全问题的多项式时间算法可能存在，但在 ZFC 中不可能证明这些算法是正确的。.然而，如果能够证明，使用目前已知适用的排序技术，即使将 Peano 整数算术公理(PA)扩展到更弱的假设，也无法决定问题，那么 NP 中的每个问题都必然存在近多项式时间算法。.因此，如果有人相信(正如大多数复杂性理论家所做的那样)并非所有 NP 问题都有高效算法，那么可以推断，用这些技术证明独立性是不可能的。此外，这个结果意味着用目前已知的技术证明独立于 PA 或 ZFC 并不比证明 NP 中所有问题的有效算法的存在更容易。
这些障碍也导致一些计算机科学家提出，P/NP问题可能独立于标准公理系统，如 ZFC (无法在其中被证明或否定)。对独立性结果的解释可以是对任何 np 完全问题都不存在多项式时间算法，这样的证明不能在(例如)中构造在 ZFC 中，np- 完全问题的多项式时间算法可能存在，但在 ZFC 中不可能证明这些算法是正确的。.然而，如果能够证明，使用目前已知适用的排序技术，即使将 Peano 整数算术公理(PA)扩展到更弱的假设，也无法决定问题，那么 NP 中的每个问题都必然存在近多项式时间算法。.因此，如果有人相信(正如大多数复杂性理论家所做的那样)并非所有 NP 问题都有高效算法，那么可以推断，用这些技术证明独立性是不可能的。此外，这个结果意味着用目前已知的技术证明独立于 PA 或 ZFC 并不比证明 NP 中所有问题的有效算法的存在更容易。
== 关于证明难度的结果 ==
尽管P=NP问题本身仍然是开放的，尽管获得了100万美元的奖金和大量的专门研究，但解决这个问题的努力已经产生了几种新技术。特别是，与P=NP问题相关的一些最富有成效的研究表明，现有的证明技术不足以回答这个问题，因此表明需要新的技术方法。
作为问题难度的额外证据，计算复杂性理论中的所有已知证明技术基本上都属于以下分类之一，其中每一种都不足以证明P≠ NP:
{| class="wikitable"
|-
!Classification
! Definition
|-
|Relativizing proofs
|Imagine a world where every algorithm is allowed to make queries to some fixed subroutine called an oracle (a black box which can answer a fixed set of questions in constant time, such as a black box that solves any given traveling salesman problem in 1 step), and the running time of the oracle is not counted against the running time of the algorithm. Most proofs (especially classical ones) apply uniformly in a world with oracles regardless of what the oracle does. These proofs are called relativizing. In 1975, Baker, Gill, and Solovay showed that P = NP with respect to some oracles, while P ≠ NP for other oracles. Since relativizing proofs can only prove statements that are uniformly true with respect to all possible oracles, this showed that relativizing techniques cannot resolve P = NP.
|-
|Natural proofs
|In 1993, Alexander Razborov and Steven Rudich defined a general class of proof techniques for circuit complexity lower bounds, called natural proofs. At the time all previously known circuit lower bounds were natural, and circuit complexity was considered a very promising approach for resolving P = NP. However, Razborov and Rudich showed that, if one-way functions exist, then no natural proof method can distinguish between P and NP. Although one-way functions have never been formally proven to exist, most mathematicians believe that they do, and a proof of their existence would be a much stronger statement than P ≠ NP. Thus it is unlikely that natural proofs alone can resolve P = NP.
|-
|Algebrizing proofs
|After the Baker-Gill-Solovay result, new non-relativizing proof techniques were successfully used to prove that IP = PSPACE. However, in 2008, Scott Aaronson and Avi Wigderson showed that the main technical tool used in the IP = PSPACE proof, known as arithmetization, was also insufficient to resolve P = NP.
|}
这些障碍是NP完全问题有用的另一个原因：如果可以为NP完全问题演示多项式时间算法，这将以上述结果不排除的方式解决P=NP问题。
这些障碍还导致一些计算机科学家提出，P对NP问题可能独立于ZFC等标准公理系统（无法在其中证明或反驳）。对独立性结果的解释可能是，任何NP完全问题都不存在多项式时间算法，并且（例如）ZFC中不能构造这样的证明，或者NP完全问题可能存在多项式时间算法，但在ZFC中不可能证明这样的算法是正确的。[44]然而，如果可以证明，使用目前已知的适用技术，即使在扩展整数运算的Peano公理（PA）的较弱假设下，问题也无法确定，那么NP中的每个问题都必然存在近似多项式时间的算法。[45]因此，如果一个人认为（正如大多数复杂性理论家所做的那样）并非NP中的所有问题都有有效的算法，那么使用这些技术证明独立性是不可能的。此外，这一结果表明，使用目前已知的技术证明独立于PA或ZFC并不比证明NP中所有问题的有效算法的存在更容易。
==Claimed solutions <span id="Deolalikar"></span>==
==Claimed solutions <span id="Deolalikar"></span>==
虽然 P/NP问题通常被认为是未解之谜，但许多业余爱好者和一些专业研究人员已经宣称了解决方案。2016年，Gerhard j. Woeginger 提出了一个列表，其中包含了62个 p = NP 的声称证明，50个 p ≠ NP 的证明，2个证明这个问题是不可证明的，还有一个证明它是不可判定的。解决 p 与 NP 问题的一些尝试受到了媒体的短暂关注，尽管这些尝试已被驳斥。
虽然 P/NP问题通常被认为是未解之谜，但许多业余爱好者和一些专业研究人员已经宣称了解决方案。2016年，Gerhard j. Woeginger 提出了一个列表，其中包含了62个 p = NP 的声称证明，50个 p ≠ NP 的证明，2个证明这个问题是不可证明的，还有一个证明它是不可判定的。解决 p 与 NP 问题的一些尝试受到了媒体的短暂关注，尽管这些尝试已被驳斥。
== 声称的解答 ==
虽然P对NP问题通常被认为是未解决的，许多业余和一些专业研究人员已经提出了解决方案。Gerhard J.Woeginger保持着一份列表，截至2016年，该列表包含62个据称是P=NP的证明，50个P的证明≠ NP，2个证明问题是不可判定的，1个证明问题是不可判定的。一些试图解决P对NP的尝试得到了媒体的短暂关注，尽管这些尝试后来遭到了驳斥。
== Logical characterizations==
== Logical characterizations==
类似地，NP 是一组可以用存在二阶逻辑表达的语言---- 也就是说，二阶逻辑限制排除关系、函数和子集上的全称量化。PH 的语言，PH，对应于所有的二阶逻辑。因此，问题“ p 是 NP 的一个适当子集”可以重新表述为“存在二阶逻辑能够描述语言(有限的线性有序结构与非平凡签名) ，一阶逻辑与最少不动点不能？“ Elvira Mayordomo。"P versus NP" Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).存在主义这个词甚至可以从前面的角色塑造中去掉，因为 p = NP 当且仅当 p = PH (正如前者建立 NP = co-NP，这反过来意味着 NP = PH)。
类似地，NP 是一组可以用存在二阶逻辑表达的语言---- 也就是说，二阶逻辑限制排除关系、函数和子集上的全称量化。PH 的语言，PH，对应于所有的二阶逻辑。因此，问题“ p 是 NP 的一个适当子集”可以重新表述为“存在二阶逻辑能够描述语言(有限的线性有序结构与非平凡签名) ，一阶逻辑与最少不动点不能？“ Elvira Mayordomo。"P versus NP" Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).存在主义这个词甚至可以从前面的角色塑造中去掉，因为 p = NP 当且仅当 p = PH (正如前者建立 NP = co-NP，这反过来意味着 NP = PH)。
== 逻辑特征 ==
由于描述的复杂性，P=NP问题可以用可表达的特定类别的逻辑语句来重新表述。
考虑包括线性次序关系的固定签名的所有有限结构语言。然后，通过添加合适的最小不动点组合符，P中的所有这些语言都可以用一阶逻辑表示。实际上，这与顺序相结合，允许定义递归函数。只要签名除了可分辨顺序关系之外，还包含至少一个谓词或函数，那么存储此类有限结构所占用的空间量实际上是结构中元素数量的多项式，这就准确地刻画了P。
类似地，NP是一组可在存在二阶逻辑中表达的语言，也就是二阶逻辑，被限制为排除关系、函数和子集上的通用量化。多项式层次结构中的语言PH对应于所有二阶逻辑。因此，问题“P是NP的适当子集”可以重新表述为“存在二阶逻辑能够描述（具有非平凡特征的有限线性有序结构的）语言，而具有最小不动点的一阶逻辑不能吗？”。甚至可以从前面的描述中删除“存在”一词，因为P=NP当且仅当P=PH（因为前者将确定NP=co-NP，这反过来意味着NP=PH）。
==Polynomial-time algorithms==
==Polynomial-time algorithms==
即使 p = NP，这种算法也是极不实用的。如果能在多项式时间内求子集和的最短程序长度为 b 位，则上述算法至少要先尝试其他程序。
即使 p = NP，这种算法也是极不实用的。如果能在多项式时间内求子集和的最短程序长度为 b 位，则上述算法至少要先尝试其他程序。
==多项式时间算法==
== 多项式时间算法 ==
已知任何NP完全问题的算法都不会在多项式时间内运行。然而，有一些已知的NP完全问题算法的性质是，如果P=NP，则该算法在接受实例时以多项式时间运行（尽管常数巨大，使得该算法不切实际）。然而，这些算法不符合多项式时间，因为它们在拒绝实例时的运行时间不是多项式时间。下面的算法就是这样一个例子，它是由Levin提出的（没有任何引用）。它正确地接受NP完全语言子集和。当且仅当P=NP:<syntaxhighlight>
// Algorithm that accepts the NP-complete language SUBSET-SUM.
//
// this is a polynomial-time algorithm if and only if P = NP.
//
// "Polynomial-time" means it returns "yes" in polynomial time when
// the answer should be "yes", and runs forever when it is "no".
//
// Input: S = a finite set of integers
// Output: "yes" if any subset of S adds up to 0.
// Runs forever with no output otherwise.
// Note: "Program number M" is the program obtained by
// writing the integer M in binary, then
// considering that string of bits to be a
// program. Every possible program can be
// generated this way, though most do nothing
// because of syntax errors.
FOR K = 1...∞
FOR M = 1...K
Run program number M for K steps with input S
IF the program outputs a list of distinct integers
AND the integers are all in S
AND the integers sum to 0
THEN
OUTPUT "yes" and HALT
</syntaxhighlight>如果且仅当P=NP，那么这是一个接受NP完全语言的多项式时间算法。“接受”意味着它在多项式时间内给出“是”的答案，但当答案为“否”时，它可以永远运行（也称为半算法）。
即使P=NP，这种算法也是非常不切实际的。如果能在多项式时间内求解子集和的最短程序是b位长，则上述算法将尝试至少2<sup>b</sup>位− 1.其他项目优先。
==Formal definitions==
==Formal definitions==