狗狗才

还记得拿扑克算命时的情形吧，把一摞扑克牌背面朝上摊在对方面前，说：“选一张出来吧。”这是个再简单不过的任务啦，他可以很容易的随意抽一张。

可要给我的电脑算命，就没那么容易了。我说：“随机的选一张牌出来吧”。哦，电脑懵了，他委屈的说：“‘随机’？我不懂！具体是哪一张牌你可没说，从来都是你明确的告诉我该做什么，我才知道怎么做的阿！”

等待我算命的人，将会抽哪张牌，我是完全不可能预料到的。可电脑是个乖孩子，他只懂得100%的执行命令，没有半点的自主权，当我把一条程序写好，或是把一条命令准备好时，电脑将怎样做，我是完全确定的。

你可能会想到“生成随机数”这样的算法来反驳我，说，瞧，这不是挺随机的么？不，这只是貌似随机罢了。拿用系统时间产生随机数的算法来说，一个确定的系统时间所能产生的“随机数”也是确定的。而真正的随机是指，他下一步将做什么，你完全不可能预料得到。

好了，你可能已经大概感觉到“确定”与“非确定”的区别了。下面我们来给一个形式化的定义：各种计算机器模型（自动机），在每一时刻，根据当时的状态和输入，若机器的动作可唯一确定时，则称机器为确定性的；若有多个动作可供选择时，则称机器为非确定性的。

如果我现在的状态是“睡觉呢”，我的输入是“闹钟响了”，如果我可能做的动作是唯一确定的“起床”，那么我是确定性的；如果我的动作是在“起床”与“继续睡”之间可以任意选择的，那么我是非确定性的。显然我是非确定性的。

非确定性的机器，目前在现实中还不存在，所以我暂时也没法给机器算命。但是为什么人们要假设，有这么一种非确定性的机器呢？他有什么特殊的用途呢？

来看这样一道题：在这个集合{2，4，6，1，8，10，-1}中，是否存在相加等于0的数。

哈，太简单了，存在，1与-1阿。你几乎是一眼就看出来了。你肯定不会依次把2+4，2+6，2+1……4+6，4+1，4+8，……10+(-1)……2+4+6……2+4+6+1……2+4+6+1+8……2+4+6+8+10+(-1)所有的这些相加的可能性全算一遍，再告诉我答案。但是机器会。实际上机器只能这样做。

只有所有可能的相加的情况都不等于0，才能确定的说“不存在”，但只要有一个相加的情况等于0，我们就可以说“存在”。看来“存在”比“不存在”更容易验证。于是我们设想一种机器，他能够在这个集合中完全“随机”的挑出一些数，相加之后来验证，一旦相加等于0，这道题就成功的解完了。这样的机器，就是上面所说的非确定型机器。他计算起这样的题来应该比确定性的机器要快的多，因为他不必“依次”的计算，而是“猜”着算。

刚才说过目前还没有现实中的非确定型的机器，但是如果这种机器永远都不可能存在，我们也就没有研究它的意义了，实际上是，他是有可能存在的，只是现在我们还造不出来。目前被人们寄予希望最大的是量子计算机。

粒子，诸如光子、电子的运动规律是量子化的，他们具有真正意义上的不确定性，人们不可能用任何方法准确的知道一个光子或一个电子下一个时刻的状态，它是随机的，人们只知道可能出现其中某一个状态的概率。打个比方，这就像，我不可能知道要算命的人抽的究竟是哪张牌，但我知道他抽到红桃A的概率是1/52。

说了这么多，确定与非确定与P与NP有什么关系呢？你可能已经猜到了，NP当中的“N”指的就是“Non-deterministic”即非确定性。

要解释清楚P与NP，还有更多的概念需要阐释，请继续关注下一篇Blog。