P/NP问题

学术定义

更正式一些，一个决定问题是一个取一些字符串为输入并要求输出为是或否的问题。若有一个算法（譬如图灵机，或一个LISP或Pascal的程序并有无限的内存）能够在最多nᵏ步内对一个串长度为n的输入给出正确答案，其中k是某个不依赖于输入串的常数，则我们称该问题可以在多项式时间内解决，并且将它置入类P。直观的讲，我们将P中的问题视为可以较快解决的问题。
现在假设有一个算法A(w,C)取两个参数，一个串w，也就是我们的决定问题的输入串，而另一个串C是“建议证明”，并且使得A在最多nᵏ步之内产生“是／否”答案（其中n是w的长度而k不依赖于w）。进一步假设：w是一个答案为“是”的例子，当且仅当，存在C使得A(w,C)返回“是”。
则我们称这个问题可以在非决定性多项式时间内解决，且将它放入NP类。我们把算法A作为一个所建议的证明的检验器，它运行足够快。（注意缩写NP代表“Non-deterministic（非确定性）Polynomial（多项式）”而不是代表“Non-Polynomial（非多项式）。）

NP完全

要解决P = NP问题，NP完全的概念非常有用。不严格的讲，NP完全问题是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。例如，旅行推销员问题的判定问题版本是NP完全的。所以NP中的任何问题的任何特例可以在多项式时间内机械地转换成旅行商问题的一个特例。
所以若旅行商问题被证明为在P内，则P  = NP。旅行商问题是很多这样的NP完全的问题之一。若任何一个NP完全的问题在P内，则可以推出P = NP。不幸的是，很多重要的问题被证明为NP完全，但没有一个有已知快速的算法。

更难的问题

虽然是否P=NP还是未知的，在P之外的问题是已经知道存在的。寻找国际象棋或围棋最佳走法（在n乘n棋盘上）是NP困难的。因为可以证明P ≠ EXPTIME（指数时间），这些问题位于P之外，所以需要比多项式时间更多的时间。判定皮尔斯伯格算术中的命题是否为真的问题更加困难。Fischer和Rabin于1974年证明每个决定Presburger命题的真伪性的算法有最少2²ᶜⁿ的运行时间，c为某个常数。这里，n是Presburger命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如停机问题。它们无法在任何给定时间内解决。

关于证明的难度的结果

虽然百万美元的奖金和投入巨大却没有实质性结果的大量研究足以显示该问题是困难的，但是还有一些形式化的结果证明为什么该问题可能很难解决。
最常被引用的结果之一是设计神谕。假想你有一个魔法机器可以解决单个问题，例如判定一个给定的数是否为质数，可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P = NP和P ≠ NP二者都可以证明。这个结论带来的后果是，任何可以通过修改神谕来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在相对化）。
如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P = NP问题。 这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类定理得到证明，该定理的可能证明方法有越来越多的陷阱要规避。
这实际上也是为什么NP完全问题有用的原因－若对于NP完全问题存在有一个多项式时间算法，或者没有一个这样的算法，这将能用一种相信不被上述结果排除在外的方法来解决P = NP问题。

多项式时间算法

没人知道多项式时间算法对于NP完全问题是否存在。但是如果这样的算法存在，我们已经知道其中的一些了！例如下面的算法正确地接受了一个NP完全语言，但是没人知道通常它需要多久运行。它是一个多项式时间算法当且仅当P = NP。
  // 接受NP完全语言的一个算法子集和。
  //
  // 这是一个多项式时间算法当且仅当P=NP。
  //
  // “多项式时间”表示它在多项式时间内返回“是”，若
  // 结果是“是”，否则永远运行。
  //
  // 输入：S = 一个自然数的有限集// 输出："是"如果某个S的子集加起来等于0。
  //         否则，它永远运行没有输出。
  // 注意:  "程序数P"是你将一个整数P写为二进制，然后
  //         将位串考虑为一个程序。
  //         每个可能的程序都可以这样产生，
  //         虽然多数什么也不做因为有语法错误。
  //         
  FOR N = 1...infinity
      FOR P = 1...N
          以S为输入运行程序数P N步
          IF程序输出一个不同的整数的列表AND所有整数都在S中
              AND整数的和为0
          THEN
              OUTPUT "是"并 停机
若P = NP，则这是一个接受一个NP完全语言的多项式时间算法。“接受”表示它在多项式时间内给出“是”的答案，但允许在答案是“否”的时候永远运行。
可能我们想要“解决”子集和问题，而不是仅仅“接受”子集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案。是否存在任何可能在多项式时间内解决这个问题的算法？没有人知道。但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的IF语句替换成下面的语句：
          IF程序输出一个完整的数学证明AND证明的每一步合法AND结论是S确实有（或者没有）一个和为0的子集THEN
              OUTPUT "是"（或者"不是"如果那被证明了）并停机

逻辑表述

P=NP问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有P中的语言可以用一阶逻辑加上最小不动点操作（实际上，这允许了递归函数的定义）来表达。类似地，NP是可以用存在性二阶逻辑来表达—也就是，在关系、函数、和子集上排除了全称量词的二阶逻辑。多项式等级，PH中的语言对应与所有的二阶逻辑。这样，“P是NP的真子集吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？”

花絮

普林斯顿大学计算机系楼将二进制代码表述的“P=NP?”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。
康奈尔大学的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：

反证法。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真。但是，因为P = NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到了矛盾。