134
个编辑
更改
跳到导航
跳到搜索
小第39行：
第39行： − 第483行：
第482行： − + − 作为问题难度的额外证据，计算复杂性理论中的所有已知证明技术基本上都属于以下分类之一，其中每一种都不足以证明P≠ NP:+ − + − + − + − + − + − + − + − + − 这些障碍是NP完全问题有用的另一个原因：如果可以为NP完全问题演示多项式时间算法，这将以上述结果不排除的方式解决P=NP问题。+ − 这些障碍还导致一些计算机科学家提出，P对NP问题可能独立于ZFC等标准公理系统（无法在其中证明或反驳）。对独立性结果的解释可能是，任何NP完全问题都不存在多项式时间算法，并且（例如）ZFC中不能构造这样的证明，或者NP完全问题可能存在多项式时间算法，但在ZFC中不可能证明这样的算法是正确的。[44]然而，如果可以证明，使用目前已知的适用技术，即使在扩展整数运算的Peano公理（PA）的较弱假设下，问题也无法确定，那么NP中的每个问题都必然存在近似多项式时间的算法。[45]因此，如果一个人认为（正如大多数复杂性理论家所做的那样）并非NP中的所有问题都有有效的算法，那么使用这些技术证明独立性是不可能的。此外，这一结果表明，使用目前已知的技术证明独立于PA或ZFC并不比证明NP中所有问题的有效算法的存在更容易。+ 第612行：
第611行： − 已知任何NP完全问题的算法都不会在多项式时间内运行。然而，有一些已知的NP完全问题算法的性质是，如果P=NP，则该算法在接受实例时以多项式时间运行（尽管常数巨大，使得该算法不切实际）。然而，这些算法不符合多项式时间，因为它们在拒绝实例时的运行时间不是多项式时间。下面的算法就是这样一个例子，它是由Levin提出的（没有任何引用）。它正确地接受NP完全语言子集和。当且仅当P=NP:<syntaxhighlight>+ − + − + − + − + − + − + − + − + − // writing the integer M in binary, then+ − // considering that string of bits to be a+ − + − − − Run program number M for K steps with input S + − + − + − + − + − + 第848行：
第845行： − +
伪代码翻译
It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution.
It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution.
P/NP问题是计算机科学领域一个尚未解决的重要问题。它想知道是否每一个问题都既可以快速验证它的解，同时也能快速求解。
P/NP问题是计算机科学领域一个尚未解决的重要问题。它想知道是否每一个问题都既可以快速验证它的解，同时也能快速求解。
== 关于证明难度的结果 ==
== 关于证明难度的结果 ==
尽管P=NP问题本身仍然是开放的，尽管获得了100万美元的奖金和大量的专门研究，但解决这个问题的努力已经产生了几种新技术。特别是，与P=NP问题相关的一些最富有成效的研究表明，现有的证明技术不足以回答这个问题，因此表明需要新的技术方法。
尽管P=NP问题本身仍然是开放的，有着100万美元的奖金和大量专门的研究，为了解决这个问题的已经产生了几种新技术。尤其是与P=NP问题相关的一些最富有成效的研究表明，现有的证明技术不足以回答这个问题，因此意味着需要新的技术方法。
作为表面问题困难的额外证据，计算复杂性理论中的所有已知的证明技术基本上都属于以下分类，它们都无法有力证明P≠ NP:
{| class="wikitable"
{| 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.
|想象一下，在一个世界里，每个算法都可以对一个名为oracle（一个可以在固定时间内回答一组固定问题的黑匣子，例如一步解决任何给定旅行商问题的黑匣子）的固定子例程进行查询，oracle的运行时间不计入算法的运行时间。大多数证明（尤其是经典证明）都适用于有神谕的世界，无论oracle做什么。这些证明被称为相对化。1975年，贝克、吉尔和索洛维证明，对于某些oracle，P=NP，而对于其他oracle，P≠ NP。由于相对化证据只能证明对所有可能的预言都一致正确的陈述，这表明相对化证据无法解决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.
|1993年，亚历山大·拉兹博罗夫（Alexander Razborov）和史蒂文·鲁迪奇（Steven Rudich）为电路复杂度下限定义了一类通用的证明技术，称为自然证明。当时，所有已知的电路下界都是自然的，电路复杂性被认为是解决P=NP的一种非常有前途的方法。然而Razborov和Razich证明如果单向函数存在，那么没有一种自然证明法可以区分P和NP。虽然单向函数从未被正式证明存在，但大多数数学家认为它们确实存在，证明它们存在的证据将比P≠ NP更有力。因此，仅自然证明不太可能解决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.
|在Baker-Gill-Solovay结果之后，新的非相对化证明技术被成功地用于证明IP=PSPACE。然而，在2008年，Scott Aaronson和Avi Wigderson证明了IP=PSPACE证明中使用的主要技术工具，即所谓的算术化，也不足以解决P=NP问题。
|}
|}
这些障碍是NP完全问题有意义的另一个原因：如果可以为NP完全问题有多项式时间算法，这将以不被以上结果排除的方式解决P=NP问题。
这些障碍还导致一些计算机科学家提出，P对NP问题可能独立于ZFC等标准公理系统（无法在其中证明或反驳）。对独立性结果的解释可能是，任何NP完全问题都不存在多项式时间算法，并且（例如）ZFC中不能构造这样的证明，或者NP完全问题可能存在多项式时间算法，但在ZFC中不可能证明这样的算法是正确的。然而，如果可以证明，使用目前已知的适用技术，即使在扩展整数运算的Peano公理（PA）的较弱假设下，问题也无法确定，那么NP中的每个问题都必然存在近似多项式时间的算法。因此，如果一个人认为（正如大多数复杂性理论家所做的那样）并非NP中的所有问题都有有效的算法，那么使用这些技术证明独立性是不可能的。此外，这一结果表明，使用目前已知的技术证明独立于PA或ZFC并不比证明NP中所有问题的有效算法的存在更容易。
==Claimed solutions <span id="Deolalikar"></span>==
==Claimed solutions <span id="Deolalikar"></span>==
== 多项式时间算法 ==
== 多项式时间算法 ==
任何已知的NP完全问题都没有多项式时间运行的算法。但是对于一些已知的NP完全问题，如果其满足P=NP这个性质，则该算法能以多项式时间接受实例（尽管常数巨大，使得该算法不切实际）。然而，这些算法并不是多项式时间的，因为它们在拒绝实例时的运行时间不是多项式时间。下面这个由Levin（没有任何引用）提出的算法就是这样一个例子。当且仅当P=NP时，它正确地接受NP完全语言SUBSET-SUM。:<syntaxhighlight>
// Algorithm that accepts the NP-complete language SUBSET-SUM.
// 接受NP完全语言SUBSET-SUM的算法。
//
//
// this is a polynomial-time algorithm if and only if P = NP.
// 当且仅当 P = NP时，它是一个多项式时间算法。
//
//
// "Polynomial-time" means it returns "yes" in polynomial time when
// "多项式时间" 意味着当答案是"yes"时，它在多项式时间内返回 "yes"
// the answer should be "yes", and runs forever when it is "no".
// 当答案是"no"时，它一直运行。
//
//
// Input: S = a finite set of integers
// 输入: S = 有限的整数集合
// Output: "yes" if any subset of S adds up to 0.
// 输出: 如果S的任何一个子集求和为0，输出"yes"。
// Runs forever with no output otherwise.
// 如果没有输出就一直运行。
// Note: "Program number M" is the program obtained by
// 注意: “M号程序”是通过将整数M以二进制形式表示，
// 然后将这些比特字符串视为一个程序得到的。
// 每一个可能的程序都可以通过这种方式生成，
// program. Every possible program can be
// 尽管由于语法错误，大多数程序什么也不做。
// generated this way, though most do nothing
// because of syntax errors.
FOR K = 1...∞
FOR K = 1...∞
FOR M = 1...K
FOR M = 1...K
输入S，运行K步M号程序
IF the program outputs a list of distinct integers
IF 程序输出一串不同的整数
AND the integers are all in S
AND 所有整数都在S中
AND the integers sum to 0
AND 这些整数相加为0
THEN
THEN
OUTPUT "yes" and HALT
OUTPUT "yes" and HALT
</syntaxhighlight>如果且仅当P=NP，那么这是一个接受NP完全语言的多项式时间算法。“接受”意味着它在多项式时间内给出“是”的答案，但当答案为“否”时，它可以永远运行（也称为半算法）。
</syntaxhighlight>当且仅当P=NP，那么这是一个接受NP完全语言的多项式时间算法。“接受”意味着它在多项式时间内给出“是”的答案，但当答案为“否”时，它可以永远运行（也称为半算法）。
即使P=NP，这种算法也是非常不切实际的。如果能在多项式时间内求解子集和的最短程序是b位长，则上述算法将尝试至少2<sup>b</sup>位− 1.其他项目优先。
即使P=NP，这个算法也非常不实用。如果能在多项式时间内求解子集和的最短程序是b位长，则上述算法将首先至少尝试其他程序2<sup>b</sup>− 1次。
==Formal definitions==
==Formal definitions==
在《基本演绎法》第二季第二集中，"求解x"围绕夏洛克和华生调查那些试图解决P/NP问题的数学家的谋杀案展开。
在《基本演绎法》第二季第二集中，"求解x"围绕夏洛克和华生调查那些试图解决P/NP问题的数学家的谋杀案展开。
<u>备注：popular culture 直译为大众文化,因以下所举内容皆为影视，而且此翻译我感觉并不地道，故修改的更加具体。对于人名我习惯不翻译，但括号中还是给出了我通过百度或谷歌翻译得到的译法。</u>
<u>备注：popular culture 直译为大众文化,因以下所举内容皆为影视，而且此翻译我感觉并不地道，故修改的更加具体。</u>
==See also==
==See also==