发信人: wasguru()
整理人: bsese(2000-05-31 10:33:41), 站内信件
|
草草翻译了一下，不当之处请指正。
P=NP是计算机科学中最著名的问题，它与费马最后定理类似，尽管P=NP问题才被
提出３０年左右，也许２５年吧。在组合算法的领域里，这个问题是这样：我们
是否有可能求解那些有2^n种可能性的问题？如果我们知道最佳的的方法，我们能
够以类似10^n这样的花费来求解这些问题吗？如果P=NP，那么答案是“能”，我
们可能把所有这些指数型的问题化简为某个多项式型的问题。如果P不等于NP，那
么答案是“不能”，我们无法化简这些问题。
我有一种感觉，有人将会以下面这种最坏的方式来解决这个难题：将会有人证明
P等于NP，因为只存在有限多种障碍使P不等于NP（笑）。结果将会是，存在某个
多项式，我们可以在这个多项式的时间内求解所有的NP问题。然而，我们并不确
切地知道这个多项式是什么样的，我们仅仅知道这个多项式存在。它的复杂性可
能高达n的一万亿次方或更高——但它仍然是一个多项式。在这种情形下，我们将
永远都无法知道这个多项式是什么，因为要找到这个多项式实在太费时了，但是
它也许是存在的。这就意味着整个P=NP的问题根本就是一个错误的问题！（笑）
事情很可能会这样。要知道，即使你有一个需要花费2^n的时间的解法，但是如果
你拿它跟另一个需要n^100时间的方法相比的话，你会发现用2^n那个算法你还可
以解n小于20或30的问题，而用n^100那个方法解n=2都不成。所以，多项式的次数
是非常重要的。有许多许多这样的算法，要证明它不存在一个多项式算法是很困
难的。我仍然觉得，费马定理是一个与此相似的问题，提出这个问题比解决这个
问题更为重要。因此，我对威尔斯定理（按：费马定理的证明）的真实感受是，
他确实做了一件非常了不起的事情，但是我希望他解决是另外一个问题！（笑）
有很多人认为，只要证明了某个问题属于NP一类的，就不应该继续研究它了，因
为很可能这个问题没有多项式解法。但是在我们开始研究NP问题之前，我们还有
一类不可解问题——根本不存在任何解法的问题。不管你花多少时间，你永远都
无法得到答案。比如给定一个图灵机，它是否最终会停下来？这是一个在一般意
义上无解的问题，不管你花多少时间。在NP问题出名之前，人们在证明了某个问
题无解之后就会放弃对它的研究。但这并不是一个好的策略，因为几乎每一个我
们已经解决的问题都是某个不可解问题的特殊情形。
拿微积分做个例子。任意给定一个n的函数f，问：当n趋向无穷大时，函数的极限
是否为0?这是一个不可解的问题。但是它不可解并不意味着我们不应该研究微积
分。许多有用的函数的极限确实是零，人们也因此而能够发展出微积分这门学科
。但是在一般意义上，这个问题是不可解的。你可以仅用寥寥数行，定义函数f的
值为0，若某给定的图灵机在时间n时已经停止，为1，若这个图灵机在时间n时还
在运行。这样，当且仅当图灵机最终会停止运行时，这个函数的极限为0。这是一
个不可解的问题。
NP的问题与此类似，有很多NP难的问题可以很好地得到求解；仅仅知道一个问题
是NP难的就放弃对它的研究可不是一个好主意。
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 144.92.44.76]
|
|