经典计算机的计算极限是多少?

发布时间：2023-04-24 08:49:00 所属栏目：动态来源：

导读：乍一看，传统计算机的运算极限似乎只是一个工程问题。传统计算机的运算极限不就决定于你能输入多少能量而不至于把芯片融化？不就决定于你在硅存储器里翻转一个比特的最高速度? 不就决定于你在一个房间大小的空间里能

乍一看，传统计算机的运算极限似乎只是一个工程问题。传统计算机的运算极限不就决定于你能输入多少能量而不至于把芯片融化？不就决定于你在硅存储器里翻转一个比特的最高速度? 不就决定于你在一个房间大小的空间里能把电脑做得多大? 所以，传统计算机的运算极限这个问题表面上看似乎并不深奥。

然而事实上，运算(computation)的概念远比怎样更好地制造一台计算机更加地抽象和基础。早在20世纪30年代中期，普林斯顿数学家阿朗佐·丘奇(Alonzo Church)和艾伦·图灵(Alan Turing)就已经证明，任何涉及比特和字节的计算都可以在一个被称为图灵机(Turing machine)的理想化计算机上完成，也就是任何传统计算都能在图灵机的框架下进行。这个结果表明所有的经典计算机本质上都等价为图灵机，这一发现使科学家和数学家能够提出关于计算机的更为基本的问题而不必纠缠于计算机架构的细枝末节。

而 NP问题则更难解决，也就是你算出结果的时间和你的运算规模n之间不再是多项式关系，比如变成指数关系：2n（严格来讲NP问题是不确定有没有多项式算法的问题，英文为：Nondeterministic polynomial problems）。NP问题虽然难以运算，但其有另外一个重要特点就是：一旦你知道了答案，检查这个答案的对错却是相对容易和快速的（可以在多项式时间内验证其解是否正确）。NP问题的一个典型例子是旅行推销员（或者邮递员、派送员）问题，即派送员需要把货物派送到一系列地点，那么他如何在这些地点上寻找一条最短的可能路线？寻找这条最短路径的运算时间和地点个数n之间似乎不再是多项式关系（显然遍历n个地点的所有路径有n!个）。因为目前所有已知的获得答案的算法都不是多项式时间，都是需要耗费大量计算资源才能完成的算法，即便面对一个派送规模n相对较小的派送问题，其强大的运算量也的确是能远远超出任何一种经典计算机的运算能力。

如果你能找到一个快速而简单的捷径来解决任何一类NP问题中最难的那个NP问题，那么你就能解决所有这类NP问题。所以从这个意义上，NP问题就会转化为P问题，但我们不确定是否存在这样的捷径和算法，也就是：是否P = NP。更为清楚的表述就是：那些在多项式时间内能被验证出答案的NP问题是否就是能在多项式时间内找到答案的P问题？然而科学家们并不认为P = NP，而数学家们要想证明这一点却并不那么容易。因为目前这个问题已经成为现代数学中难度最大的或者说是一个未解之谜，被美国著名克雷数学研究所(Clay Mathematics Institute, 简称CMI)列为千禧年七大数学问题之一。

（编辑：汽车网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!