计算机无所不能？目前还做不到

简单问题不简单

如何找出「 x ² -2x-15=0」的整数解，在课本里就能在一元二次方程式章节看过类似的题目，对于某些熟悉的人来说或许只要透过心算即可解决，然而这道看似初阶的题目真的有那么简单吗？我们都知道简单与否是因人而异的，那么对于电脑来说，要解这道题目也是简单的吗？

归功于电脑强大的计算能力，有些较单纯的数学问题透过wolfram alpha等运算平台只消片刻就能获得答案。在这看似不费吹灰之力的过程背后，由于无法和人类一样进行抽象思考以及纸笔运算，电脑其实仰赖许多演算法来应对不同的数学问题。无论是采取哪种方法，选择每一个方法的背后都有其数学的理由，譬如要解开前述一元二次方程式的题目，可以透过暴力法进行搜索，也可以透过因数法测试因数分解后得到可能的候选值再进行判断，又或者可以利用因式法直接进行因式分解得到答案，这些不同的方法背后都有其数学定理支撑。

希尔伯特第十问题的答案

让我们更进阶一点，思考如何找出「x ² -631y ² -1=0」的所有整数解，或许有人一眼就能看出来，(x,y)=( ±1,0)即为两组解，不过下一组整数解的数量级已经暴涨至x=48,961,575,312,998,650,035,560、y=1,949,129,537,575,151,036,427。由此可以看出，即使只是一个简单系数的二元二次方程式，解答很容易就落在多数人计算范围之外，面对这类问题，我们可以寄希望于电脑吗？这个问题的答案令人惊讶，至今为止「没有方法」可解所有的二元整数方程式。

十九世纪末，德国数学家希尔伯特(David Hilbert, 1862-1943)提出了二十三道数学问题，期望能在接下来的二十世纪中获得回应。其中，第十道问题即是询问「是否能找到一个方法，可以在有限的步骤内，决定任一个整数方程式是否有整数解？」，这个问题在数学家的努力下，得到的答案是「没有方法」(MRDP定理)，这个答案很有趣，说不定也出于当年希尔伯特的意料之外，而这个「没有方法」究竟是什么意思？这个方法究竟存不存在？现在不知道难道以后也不知道吗？

任何电脑能够执行的工作都是图灵机可算的问题，根据邱池—图灵论题(Church—Turing thesis)，任何可计算的问题，都是图灵机可算的，相对的那些图灵机不可算的问题，就是被认为「没有方法」可以解决的问题。所谓的「没有方法」并不等同「方法存在只是还没找到」，更精确一点的说，其实就是「这个方法不存在」，如果从计算的角度来说，「没有方法」指得就是无论未来电脑如何发展，给予不受限制的时间与资源仍无法透过电脑解决。这一类和方程式整数解一样「没有方法」、电脑无法解决的问题，我们就称作是「不可算问题」。

P = NP?

前述针对可计算性的讨论，通常是不限时间与空间的，不过现实中所会碰到的问题常常会需要在受限的时间以及记忆体空间下解决，在此种状况下，需要考虑计算繁度，换句话说，我们除了思考有没有方法，也想探究有没有足够好的方法。要比较不同方法的好坏，作为衡量基准的，通常是当问题变得非常复杂时，解决问题所需要花费的时间。

图灵机可以被分成确定型(deterministic)和不确定型(non-deterministic)两类，前者即是一般通称的图灵机，在运作中由当前的值和状态决定下一步，因此下一步只有一种可能，这也是目前电脑普遍运作的方式；后者则是在选择下一步时，同时有多种可能的路径可以选择。要注意的是，这两种图灵机可以解决的问题是一样多的，差别在于两者之间所需要的时间不一样。如果一个问题，可以被确定型图灵机在多项式时间被解决的话，这一类问题我们就称为「可行(feasible)问题」，一般以P来表示；相对的，不在P中的这类问题就是「非可行(Infeasible)问题」，可以被非确定型图灵机在多项式时间被解决的话，这一类问题我们就称为NP问题，另外，NP否定问题称为CO-NP问题。在NP问题中，最难的一类问题被称为NP完备(NP-Complete, NPC)，其否定问题则称作CO-NPC。

当今对计算繁度的分类有多种猜测，而其中被认为是电脑科学及数学最重要的问题之一的，即是P是否等同于NP (P=NP?)，被列入克雷数学研究所(Clay Mathematics Institute，CMI)悬赏一百万美金的七道千禧年大奖难题之中。P是否等于NP和数位时代的生活息息相关，现在常用的RSA加密演算法其核心是由质数乘积来加密，质数乘积一般被认为是一个陷阱函数，也就是计算容易但逆转计算相当困难的函数，破解密码需要质因数分解这是个NP问题，一旦我们可以证明NP等于P，就可以将NP转换成P问题来处理，破解密码将会成为可行问题，对现行的资讯安全将会造成极大的威胁。

在当前的电脑架构下，大部分电脑科学家的看法为，因此，若一个问题已经被证明为NP完备，其求最佳解则被认为非可行，遇到这一类非可行问题，随着问题的复杂度增加，即使目前电脑运算速度成长日新月异，计算能力提升所带来的解题效率也无法显著提升。

量子计算增添计算科学的样貌

量子计算近年来成为热门的领域，在确定型图灵机以外开创一条不同的计算形式。虽然量子计算的可算性与确定型图灵机相同，不过量子计算的可行性与确定型图灵机可能有所不同，所以也多了一种衡量计算繁度的指标，称为BQP(Bounded-error Quantum Polynomial Time)。譬如，对于传统图灵机来说是NP的因数分解问题，就有多项式时间的BQP量子演算法，因此有人猜测因数分解可以成为可行问题，如果这个猜测在未来被证实了，就如上述，传统上使用RSA加密的资讯就需要另寻他路来保护资料安全。

电脑的运算能力进入二十一世纪以来显著成长，受惠于此许多研究、工程领域产生不少应用，让我们的生活更便利。在应用端，一如前面提过的寻找整数解、质因数分解等问题，回到最源头的数论、计算科学仍有许多有趣的、重要的问题等待探索，这些问题能否被解决、有没有答案，将会决定下个世代计算的面貌。