凯伦·a·弗兰克尔著
ACM通讯，1986年2月，第29卷第2期，第110-111页
10.1145/5657.214905
评论
为了说明“复杂性理论通过可计算性理论的类比来运作的显著程度”，Richard Karp创建了这个概念地图或拼图游戏。为了在平面上布置谜题，他使用了“图平面算法”。距离较远的部分乍一看可能没有关联，“但最终，np完备性理论确实将它们结合在了一起，”卡普说。
谜题的右上角显示了与组合爆炸和“好”或“有效”算法相关的概念。反过来，“复杂性”将这些概念与左上部分联系起来，这代表了早期可计算理论家的关注点。
旅行推销员问题更接近右上角，因为它可能难以处理。因此，它接近于“np完备性”和“组合爆炸”。
然而，在某种程度上，某些划分是模糊的。例如，“线性规划”就有一种反常的状态——在实践中用于解决这类问题的最广泛使用的算法在理论意义上并不好，而那些在理论意义上很好的算法在实践中往往并不好。六年前备受关注的椭球法就是一个例子。它在多项式时间内运行，但多项式的次数如此之高，该方法在技术意义上被证明是好的，但在实践中是无效的。“原因是我们关于多项式时间算法的概念并没有完全抓住直观高效算法的概念，”Karp解释道。“当你起床的时候
n
5或
n
6，那么就很难证明它真的有效。所以埃德蒙兹关于好的算法的概念并不是直观意义上的好的完美形式对应。”此外，单纯形算法在每一个实际意义上都很好，Karp说，但根据复杂性理论的标准范式并不好。Karp说，线性规划解决方案的最新补充，是由Narendra Karmarkar设计的一种算法，一些人认为它挑战了单纯形算法，它在技术意义上很好，在实践中似乎也相当有效。
好的算法部分与“启发式”相邻，因为启发式算法可能工作得很好，但缺乏理论谱系。一些启发式算法总是快速的，但有时不能给出好的解。其他人总是给出一个最优解，但不保证是快速的。单纯形算法属于后者。
“不确定性”、“组合爆炸”和“复杂性”在同一个平面上，因为它们是彼此的类似物;不可判定性涉及无界搜索，而组合爆炸根据定义是非常长的但不是无界搜索。复杂性理论弥补了这一差距，因为它不是问一个问题是否能被解决，而是提出了关于问题的问题
资源需要解决一个问题。
左下方区域包含了Karp最近关注的部分，其中包含了开放式问题。例如，“随机算法”与“概率分析”相对，因为两者都是确定性算法的最差情况分析的替代方案。随机算法可能能够在多项式时间内解决确定性算法无法解决的问题，这可能意味着好算法概念的扩展。也许通过对非冯·诺依曼机器的软件设计，算法可以通过并行性在实践中变得更高效。最后，这个谜题的某些部分还没有定义。卡普说:“它们对应着未来有待探索的未知领域。”
这篇文章的全文是优质内容
没有找到条目
登录阅读全文
需要访问吗?
请选择以下其中一个选项以访问优质内容和功能。
创建一个网络帐户
如果您已经是ACM会员，通信订阅用户，或数码图书馆订阅用户，请设立网上帐户，以便阅览本网站的优质内容。
加入ACM
成为ACM会员可以充分利用ACM卓越的计算信息资源、网络机会和其他优势。
订阅ACM杂志通讯
获得完全访问超过50年的CACM内容，并每月收到印刷版杂志。
购买物品
非会员可以购买这篇文章或它出现的杂志的副本。
