为什么有些问题不能解决?(1) 一些问题没有解决的方法(算法);(2) 一些问题有解 决的方法(算法),但随着问题的尺度的增加,无法算下去。 第一类问题中典型的例子是图灵(TURING)停止问题:是否存在一个程序,它可以用 来判断另一个程序是死循环(不停地运行)或停止。一般来说,这样的程序是不存在 的。如果存在这样的程序H,它可以用来判断另一个程序P,H(P):H将P作为输入。 我们可以根据H(P)的判断结果来设计另一个程序G(H(P)):当H(P)认为P是死循环时, G停止;当H(P)认为P是停止时,G死循环。SO FAR,SO GOOD。但当我们用G来代替P, 即用上述程序来判断程序G,G(H(G)),我们就进入悖论怪圈。里面的G是死循环,外 面的G是停止;里面的G是停止,外面的G是死循环。实际上里面的G和外面的G是同一 个G。所以,一般来说,程序H是不存在的。在计算机理论中,常有一些递归不能解 决问题。所谓“递归”是指“对自己”,即一些算法“对自己”不灵,“对别人” 可以。 这一类问题还有很多,比较著名的是贴砖(TILING)问题。给出一组有限种类的砖(数 量是无限),问是否存在一个算法,它能确定是否这些砖能铺满座标系的第一象限。 贴砖时,砖子不能旋转,砖子之间还得符合邻接条件。贴砖的程序可以转换为图灵 机程序。于是贴砖问题就转换为图灵停止问题。因此这样的算法是不存在。 第二类问题也有很多,现举一个旅行商问题。旅行商问题:有N个城市,一个推销员 要从某一个城市出发,走遍所有的城市(一个城市只能去一次),再回到他出发的城 市,求长度小于或等于K的路线。这个问题属于NP问题,即非确定性多项式时间问题。 所谓NP问题是指,有一个非确定型计算机,它可以得到问题的解,而且每一步程序 都是正确的;(实际上,世界上还没有这种计算机) 然后只需用多项式时间来证实这 个问题的解。对于旅行商问题,非确定型计算机已经得到它的解,证实这个解实际 上只需多项式时间。当然,用确定型计算机求解这个问题,就需要(N-1)阶乘时间, 因此当N很大时,无法算下去。对于旅行商问题,如果我们要证实没有长度小于或等 于K的路线,这就不是NP问题,因为我们要枚举所有的情况。这时,这个问题属于CO-NP问题。 在研究工作中,我们经常碰到这样的情况,当问题的尺度比较小时,理论很优美, 计算也简单;当问题的尺度比较大时,就无法搞下去。 |