解释计算复杂性理论

假设有一些数学背景,你会如何对天真的计算复杂性理论进行总体概述？

我正在寻找P = NP问题的解释.什么是P？什么是NP？什么是NP-Hard？

有时维基百科的编写就像读者已经理解了所涉及的所有概念一样.

Hoooo,博士学位闪回.好的,这里有.

我们从一个决策问题的想法开始,一个算法总能回答"是"或"否"的问题.我们还需要两种计算机模型(图灵机,真的)的概念:确定性和非确定性.确定性计算机是我们一直在思考的常规计算机; 一个非确定性的计算机就像我们习惯的那样,除了它具有无限的并行性,因此无论何时你来到一个分支,你都会产生一个新的"过程"并检查双方.就像Yogi Berra所说的那样,当你来到路上的叉子时,你应该接受它.

如果存在已知的多项式时间算法来得到该答案,则决策问题在P中.如果存在用于非确定性机器的已知多项式时间算法以获得答案,则决策问题在NP中.

已知在P中的问题在NP中是非常简单的 - 非确定性机器从不会麻烦自己分叉另一个过程,并且就像确定性过程一样.已知存在P和NP都不存在的问题; 一个简单的例子是枚举长度为n的所有位向量.无论如何,这需要2 ^个步骤.

(严格地说,如果节点终结机器可以在多时间内得到答案,则决策问题在NP中,并且确定性机器可以在聚合时间内验证解决方案是正确的.)

但是在NP中已知存在一些问题,其中没有多时间确定性算法; 换句话说,我们知道他们在NP中,但不知道他们是否在P中.传统的例子是旅行商问题(decision-TSP)的决策问题版本:给定城市和距离,是否有一条覆盖所有城市的路线,返回起点,距离不到x？在一个不确定性的机器上这很容易,因为每当不确定性的旅行推销员来到路上的叉子时,他就会接受它:他的克隆人前往他们没有去过的下一个城市,最后他们比较笔记,看看是否任何克隆都需要不到x的距离.

(然后,指数级的克隆人必须对抗哪些克隆必须被杀死.)

目前尚不清楚决策TSP是否在P中:没有已知的多时间解决方案,但没有证据证明这种解决方案不存在.

现在,还有一个概念:给定决策问题P和Q,如果算法可以在多项式时间内将P的解转换为Q的解,那么可以说Q是多时间可缩减的(或者只是可简化的)到P.

如果你能证明(1)它在NP中,并且(2)表明它的多时间可以简化为已知为NP完全的问题,则问题是NP完全的.(其中最难的部分是NP完全问题的第一个例子:这是史蒂夫库克在库克定理中完成的.)

因此,其实,它说的是,如果有谁发现聚一次解决一个NP完全问题,他们已经自动获得了一个一个为所有的NP完全问题; 这也意味着P = NP.

一个问题是NP难的,当且仅当它"至少和NP完全问题一样难"时.寻找最短路线的传统旅行商问题是NP难的,而不是严格的NP完全.

Michael Sipser的 " 计算理论导论"是一本很好的书,而且非常易读.另一个重要的资源是Scott Aaronson的理论计算机科学课程.

使用的形式主义是查看决策问题(是/否答案的问题,例如"这个图表是否具有汉密尔顿循环")作为"语言" - 字符串集 - 答案为是的输入.有一个关于"计算机"是什么的正式概念(图灵机),如果存在用于在图灵机上确定该问题(给定输入字符串,说是或否)的多项式时间算法,则存在问题.

如果在多项式时间内可检查,则问题出现在NP 中,即如果对于答案为是的输入,则给出(多项式大小)证书,您可以在多项式时间内检查答案为是.[例如,给定哈密顿循环作为证书,您显然可以检查它是否为.]

它没有说明如何找到该证书.显然,您可以尝试"所有可能的证书",但这可能需要指数时间; 目前尚不清楚是否会一直有拿比多项式时间更多的决定是或否; 这是P vs NP问题.

如果能够解决该问题意味着能够解决NP中的所有问题,那么问题就是NP难.

另见这个问题: 什么是计算机科学的NP-complete？

但实际上,所有这些可能只对你含糊不清; 值得花时间阅读例如Sipser的书.这是一个美丽的理论.

这是对查理的帖子的评论.

如果你能证明(1)它在NP中,并且(2)表明它的多时间可以简化为已知为NP完全的问题,则问题是NP完全的.

第二个条件有一个微妙的错误.实际上,你需要证明的是,一个已知的NP完全问题(比如Y)是多项式时间可以简化为这个问题(我们称之为问题X).

这种证明方式背后的原因是,如果你可以将NP问题减少到这个问题,并以某种方式设法在多时间内解决这个问题,那么你也成功地找到了NP的多时间解决方案-完整的问题,这将是一个非凡的(如果不是不可能的)事情,从那时起你将成功地解决长期存在的P = NP问题.

另一种看待这种证明的方法是将其视为使用反对证明技术,该技术基本上表明如果Y - > X,那么〜X - > ~Y.换句话说,不能在多项式时间内求解Y也不可能意味着在多时间内也不能解决X. 另一方面,如果你可以在多时间内解决X,那么你也可以在多时间内解决Y. 此外,您可以通过传递性解决在多时间内减少到Y的所有问题.

我希望我上面的解释足够清楚.一个很好的资料来源是Kleinberg和Tardos 的算法设计第8章或Cormen等人的第34章.