图灵的理论告诉我们,这个世界上只有三类问题,一种叫“可计算”的问题(比如算去年的所得税,哈哈)。就是能够在合理有限时间内(严格讲叫“多项式时间(P)”内),有步骤地(既可编程地)最终解决,图灵证明了,凡这类问题都可用图灵机求解。相反,另一类问题就是“不可计算”的问题,即不能在有限时间内,有步骤地求解,这类问题图灵机不能求解 (比如爱情问题宗教问题,哈哈)。第三类问题,也是最让科学家们头疼的问题,是这些问题目前属于“中间灰色地带”,不知道他们是“可计算的”,还是“不可计算”的,叫做“NP-完全问题”。比如过去的四色定理问题,推销员问题等等。所以,现在一旦某个NP-完全问题被证明是属于可计算的或不可计算的,都会是科学界的盛事,因为这个问题的结局会导致同类一大堆问题的命运(即能否用计算机最终解决)。以上当然是通俗非严谨的说法。有兴趣的同学可以去选修一门“计算复杂性”的CS课。哈哈
楼主的文章很好,尤其是介绍密码机原理部分。谢谢。
楼主的文章很好,尤其是介绍密码机原理部分。谢谢。