系列: 理论计算机初步

这是我在读博士期间( 2005 年 9 月到 2009 年 7 月)写的对理论计算机的介绍文章,当初雄心勃勃地想对这个领域做一个全面的介绍,后来受到水平和时间的限制,只写了少数几篇,只介绍了一些 P/NP 和算法的最基本的概念。

  1. 我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是 Andrew Yao 的研究方向
  2. 上篇文章 已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP- 完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
  3. 前面 已经提到了显示中大多数难解问题问题最后都被证明是 NP- 完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在 这篇文章 提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
  4. 密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作,不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》,在媒体上又掀起了一轮宣传狂潮,但是有些报道极端弱智,错误百出,所以我趁机纠正一下,并介绍密码学的一个组成部分 ——hash 函数,以及王小云老师在这上面的工作。