密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在hash函数破解上做出重大贡献的王小云教授的工作，不过前两天王小云获得求是杰出科学家奖以及100万奖金，在媒体上又掀起了一轮宣传狂潮，但是有些报道极端弱智，错误百出，所以我趁机纠正一下，并介绍密码学的一个组成部分——hash函数，以及王小云在这上面的工作。
王小云的主要工作是关...

前面已经提到了显示中大多数难解问题问题最后都被证明是NP-完全问题。这意味着，除非NP=P，它们是不可能有多项式时间算法的（而且，在这篇文章提到即使NP=P，人们也可能找不到一个NP完全问题的“有效”算法）。
所以人们发展了各种工具来避开它们，最常用的两种方法是使用概率算法和近似算法，这两种方法也符合实际需要：在解决实际问题中，我们不需要结果...

上篇文章已经提到，P vs NP是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有关的的学术领域中，NP-完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独立的智力游戏，而是对计算机科学有全面影响力的问题。
历史上的进展
从上个世界70年...

P = NP?
这个问题，作为理论计算机科学的核心问题，其声名早已经超越了这个领域。它是Clay研究所的七个百万美元大奖问题之一，在2006国际数学家大会上，它是某个1小时讲座的主题。
要说起P和NP是什么东西，得先从算法的多项式时间复杂度谈起，注意，这里面的两个P都是指Polynomial。
一个问题的规模指的是输入的总位数，比如一个n个数的排序问题，输入规模...

这段时间Blog的更新频率大大降低，因为发现没啥好写的，也没有写文章的欲望。前段时间提到了我加入中国赛客联盟，而且给的说明语是"算机|数学|算法|复杂理论"，翻了一下我这个blog，觉得有些名不副实。所以决定写一些我的专业的介绍性文章，顺便充实一下本blog的内容。
我所学的专业英文名是Theoretical Computer Science，理论计算机科学，在这里我就简化成理论计算机...