主题：【原创】ｐ（多项式算法）问题对ｎｐ（非多项式算法）问题 -- 香山居士
家园 【原创】ｐ（多项式算法）问题对ｎｐ（非多项式算法）问题 这个正好撞到我的专业上了,写一些让大家了解一下.由于我在国内不是学计算机的,出国以后转的行,文中我会用一些英文专业术语.
1. 算法的Complexity
一般一个算法的Complexity包括两个方面:一个是时间Complexity,就是解决一个问题要花多少时间;另一个是空间Complexity,考虑的是解决这个问题要用多少计算机资源,如内存等.在本文中我们只考虑时间Complexity.实际上,一般情况下p和np指的就是时间Complexity.
首先举一个例子:我们要做以下的一个矩阵-向量乘法:
y=Ax
其中A是一个n*n矩阵,x,y都是n*1的向量.如果我们直接按照矩阵乘法的定义计算,我们需要花多少时间?
让我们来算算.假设A,x,y全是实数那么按照定义,计算每一个元素要做n次乘法和n-1加法,即2n-1次基本运算(在次我们认为实数的加法和乘法都是计算机的基本运算).那么计算出整个y就需要n*(2n-1)=2n^2-n次基本运算.
同时假设在计算机运算中,每次基本运算需要相同的时间,把这个时间设为单位时间,那么前面的算法就需要花(2n^2-n)的时间来计算.
在计算机科学中,我们通常只取最高次项,同时忽略常数系数.这是因为当n很大时,低次项的贡献就可以被忽略了.回到我们前面的例子,矩阵-向量乘法的运行时间就是n平方量级,记为O(n^2).
2. p（多项式算法）问题
对于一个给定问题,如果我们可以找到一个算法在O(n^C)(C可以是任何常数)的时间内解决,那么我们称这个问题属于P问题.一般认为在实际应用中,P问题是可以解决的,无论n(输入)有多大.
如果我们找到的算法大于O(n^C),比如说O(2^n)(指数函数)和O(n!)(阶乘函数),虽然理论上这个问题可解,但实际应用中只要输入量(n)大一点,就没办法了.
假设有两个算法,一个O(n^2)另一个O(2^n).同时有一台计算机的速度是一秒钟一百万次运算.当n=1时算法1需要1微秒,算法2需要两微秒,没什么差别.但是当n=1,000,000时算法1需要一百万秒,大约是十一天半,虽然很长但还能等.算法2就需要大约(10^29994)秒,而一年不过3.15*10^8秒!
3. ｎｐ（非多项式算法）问题
很不幸,现在我们有很多问题,没有一个人可以找到O(n^C)的算法,但又没有一个人可以证明这个问题不存在O(n^C)的算法.这一类问题统称为NP问题.
已知的著名NP问题包括SAT Problem,TSP(Travelling Salesman Problem),Clique Problem, Subset Sum Problem 等.我不想在这说太多细节.但是有一点一定要提的就是,所有的NP问题都可以互相推倒出来.也就是说:
如果你解决了一个NP问题,你就解决了所有的NP问题!
记得我老师上课时说:"If you solve this problem, you will be the most famous guy in computer science."
4. 近似算法
好,现在我有一堆NP问题,我不知道如何找到最佳答案,但这些问题又太重要而无法置之不理,怎么办?别着急,人们已经找到了一些近似算法.
所谓近似算法,就是一些算法在O(n^C)时间内,给出了离最佳值"差不多"的结果.注意:在这个过程中我不知道最佳值是多少,但我知道我的结果和最佳值的差别不会太大!
这里好象有点悬,这正是近似算法最难的地方.以下以 Knapsack 问题为例简单说一下近似算法:
我有一条船,载重量100吨,有一大堆箱子,里面放满了各种金银珠宝.每个箱子有自己的重量和价值.我当然想能拿多少拿多少,但很可惜,我的船只能运100吨,多了要沉船.问题是:给定每个箱子的重量和价值,我最多能拿多少?
这是一个NP问题,我们没有办法知道最佳值--我最多能拿多少,但现在已经有了近似算法可以确切地告诉我:你按我的方法选箱子,我保证你拿的多于最佳值的一半. 那么,两倍,就是这个算法的"近似程度".
本帖一共被 4 帖 引用 (帖内工具实现)家园 NP-Complete problems are only a subset of NP problems.
when you talk "如果你解决了一个NP问题,你就解决了所有的NP问题!", you are talking about NO-Complete problems. In fact, there are many hard problems which have no NP algorithms to solve them, and they are so far not proven to be NP-Complete.
correct me, if i am wrong.
家园 没想到我这么老的一个帖子被顶上来了 你说的没错，我写的不太严格。
家园 我也曾经想当然的以为ｎｐ是代表非多项式算法 后来学了才知道，是指nondeterministic polynomial，也就是非确定性的计算机（比如量子计算机）能在多项式时间内解决。想来和我一样犯这个错误的人不少，大家一起红一下脸吧
P与NP这个看上去这么显然的问题这么久悬而未决，想来跟世界的一些根本性质有关。哪天我们理解了量子，大概就理解这个问题了；反过来也一样。
家园 讲得很清楚，离散优化有学过，P和NP问题的确很重要 离散数学中这个问题被阐述，是算法研究进了一大步。近似算法的理论基础
家园 同行, 这个要顶 有人说Computer Science只有trick, 唯一可称为Science的就是P or NP.
家园 【不明白】“如果你解决了一个NP问题,你就解决了所有的NP问题!” 前面关于算法复杂性的说明很通俗，这个。。。
家园 其实在离散数学当中，真正难的并不是算法本身 而是证明算法的合理性。NP问题不可证明性在于问题的复杂性超出了我们所掌握的数学工具的处理能力。如果你能够证明这个问题事实上是等于你提供出了新的数学工具。依靠这个当然也可以证明其他所有问题。
家园 似懂非懂地顶一下 家园 近似解和多项式拟合 理论俺不懂.如果在某一小区域找近似解,多项式拟合是很不错的选择,取到X的4,5次方足够了.实在不行,就取对数.一堆数据,取上几次对数,大多能找到一个线性关系.
居士是做应用数学的?厉害.