P类问题

时间 : 18-10-29 栏目 : ag电子捕鱼 作者 : admin 评论 : 0 点击 : 192 次

  是在理论信息学中计算复杂度理论领域里至今未被解决的问题,也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克(Stephen A. Cook)和Leonid Levin相对独立地提出了下面的问题,即复杂度类P和NP是否是恒等的(P=NP?)。

  复杂度类P即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题;类NP由所有可以在多项式时间内验证它的解是否正确的决定问题组成,或者等效的说,那些可以在非确定型图灵机上在多项式时间内找出解的问题的集合。很可能,计算理论最大的未解决问题就是关于这两类的关系的:P和NP相等。

  在2002年对于100研究者的调查,61人相信答案是否定的,9个相信答案是肯定的,22个不确定,而8个相信该问题可能和现在所接受的公理独立,所以不可能证明或证否。对于正确的解答,有一个1,000,000美元的奖励。

  NP-完全问题(或者叫NPC)的集合在这个讨论中有重大作用,它们可以大致的被描述为那些在NP中最不像在P中的(确切定义细节请参看NP-完全理论)。计算机科学家现在相信P,NP,和NPC类之间的关系如图中所示,其中P和NPC类不交。

  简单来说,P=NP问题问道:如果实然问题的正面答案可以很快验证,其答案是否也可以很快计算?

  给定一个大数Y,我们可以问Y是否是复合数。例如,我们可能问是否有非平凡的因数。 答案是肯定的,虽然手工找出一个因数很麻烦。从另一个方面讲,如果有人声称答案是对,因为224737可以整除,则我们可以很快用一个除法来验证。 验证一个数是除数比找出一个明显除数来简单得多。用于验证一个正面答案所需的信息也称为证明。 所以我们的结论是,给定正确的证明,问题的正面答案可以很快地(也就是,在多项式时间内)验证,而这就是这个问题属于NP的原因。

  虽然这个特定的问题,最近也被证明为在P类中(参看下面的关于质数在P中的参考),这一点也不明显,而且有很多类似的问题相信不属于类P。

  像上面这样,把问题限制到“是/不是”问题并没有改变原问题(即没有降低难度);即使我们允许更复杂的答案,最后的问题(是否FP=FNP)是等价的。1

  更正式一些,一个决定问题是一个取一些字符串为输入并要求输出为是或否的问题。若有一个算法(譬如图灵机,或一个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(非多项式)。)1

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

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

  上面所有的讨论,假设了P表示“容易”而“不在P中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设,它在实践中却不总是真的,原因包括如下几点:

  它忽略了常数因子。一个需要10n时间的问题是属于P的(它是线性时间的),但是事实上完全无法处理。一个需要102时间的问题不是在P中的(它是指数时间的),但是对于n取值直到几千时还是很容易处理的。

  它忽略了指数的大小。一个时间复杂度n属于P,但是很难对付。已经证明在P中存在需要任意大的指数的问题(参看时间层次定理)。一个时间复杂度2的问题不属于P,但对于n直到几千还是容易应对的。

  它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间n中解决,但是很偶尔你会看到需要时间2的特例。这个问题可能有一个多项式的平均时间,但最坏情况是指数式的,所以该问题不属于P。

  它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能,但是确保正确的答案会难得多。这个问题不会属于P,虽然事实上它可以很快求解。这实际上是解决属于NP而还不知道是否属于P的问题的一个办法(参看RP,BPP)。

  新的诸如量子计算机这样的计算模型,可能可以快速的解决一些尚未知道是否属于P的问题;但是,没有一个它们已知能够解决的问题是NP完全的。不过,必须注意到P和NP问题的定义是采用像图灵机这样的经典计算模型的术语表述的。所以,即使一个量子计算机算法被发现能够有效的解决一个NP完全问题,我们只是有了一个快速解决困难问题的实际方法,而不是数学类P和NP相等的证明。1

  虽然百万美元的奖金和投入巨大却没有实质性结果的大量研究足以显示该问题是困难的,但是还有一些形式化的结果证明为什么该问题可能很难解决。

  最常被引用的结果之一是设计神谕。假想你有一个魔法机器可以解决单个问题,例如判定一个给定的数是否为质数,可以瞬间解决这个问题。我们的新问题是,若我们被允许任意利用这个机器,是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题?结果是,依赖于机器能解决的问题,P=NP和P≠NP二者都可以证明。这个结论带来的后果是,任何可以通过修改神谕来证明该机器的存在性的结果不能解决问题。不幸的是,几乎所有经典的方法和大部分已知的方法可以这样修改(我们称它们在相对化)。

  如果这还不算太糟的线年Razborov和Rudich证明的一个结果表明,给定一个特定的可信的假设,在某种意义下“自然”的证明不能解决P=NP问题。1

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

  这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类定理得到证明,该定理的可能证明方法有越来越多的陷阱要规避。

  这实际上也是为什么NP完全问题有用的原因:若对于NP完全问题存在有一个多项式时间算法,或者没有一个这样的算法,这将能用一种相信不被上述结果排除在外的方法来解决P=NP问题。2

本文标签

除非注明,文章均为( admin )原创,转载请保留链接: http://www.treslola.com/?p=63

P类问题:等您坐沙发呢!

发表评论


-----===== 博主信息 =====-----

为您推荐

0