标签： 理论计算机

1. 通讯复杂性简单介绍
   2008-09-17, 计算机科学 » 理论计算机, 通讯复杂性

   英文是 communication complexity ，不知道该翻译成通信复杂性，还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域，在过去 30 年衍生了很多东西。它是我的研究的主要内容，这里简略介绍一下。
2. 理论计算机初步：概率算法和近似算法
   2006-09-14, 计算机科学 » 概率算法, 理论计算机, 近似算法, 理论计算机初步

   前面已经提到了显示中大多数难解问题问题最后都被证明是 NP-完全问题。这意味着，除非 NP=P ，它们是不可能有多项式时间算法的（而且，在这篇文章提到即使 NP=P ，人们也可能找不到一个 NP 完全问题的「有效」算法）。
3. 理论计算机初步：算法和计算模型
   2006-08-16, 计算机科学 » 理论计算机, 理论计算机初步

   下面是 wikipedia 上算法的定义：