科学，人文，民主
阅微堂»计算机科学
更新：证明的关键一步发现错误，作者更新了论文，结论甚至论文标题都改了（废话），新版本On the graph isomorphism problem。 提交论文到arxiv不需要审阅，一般人都可以提交，所以常有些错误的论文甚至民科作品（在物理和数学领域更多一点）。号称解决图同构问题甚至p vs np以前也有过，不过这次文章的作者的publication记录不错，有2篇ann. of Math.，数量也不少，所以大家稍微关注...
Game Theory即博弈论，目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年，理论计算机界对它的研究也很热。 Game Theory主要是研究在两人甚至多人的系统中，各方如何选择自己的策略使自己的效益最大化。这里每个人的收益不光决定于自己的决策，还决定于其它人的决策。主要有两种不同的游戏，一种是两人零和游戏，只一个人赢的...
在从hash函数到王小云的MD5破解我们介绍了hash函数的一些基本概念和MD5碰撞的一个"应用"，最近在这个问题上又有了新的进展。 Marc Stevens, Arjen Lenstra和Benne de Weger在这篇论文里给出了寻找Chosen-prefix碰撞的有效方法，这种碰撞指对任意给定的A, B，找到x, y，使得MD5(Ax) = MD5(By)，即可以找到碰撞，使得以任意两个字符串开头。 作者给出了两个非常有意思的应用，一个是预测200...
好久没有写我的理论计算机初步系列了，其实复杂性这一块，虽然平时经常遇到，但由于问题都过于本质和困难，想这方面问题的时间反而不多。Ko教授就跟我说也许NP verse P这个题并不难，只不过大家认为它很难，结果就没有多少人去做了，大家一遇到这个问题都远远得绕开。话虽如此，我还是不敢去碰的。 很多人一看到NP-hard，就从字面上理解成为比NP还难的问题。但如果这...
Though I said that I was a PH.D student, I rarely talk about MY research on this blog because first I don't want to make this blog to be too personal and second I didn't get any academic progress yet. But today I'll show something about my research, because I passed my PH.D proposal last week. [......
理论计算机(I)课上讲的一个问题，很有意思。 已经一个n，m和里n个数，设计一种保存这n个元素的表的数据结构形式，使得对中任何一个数，可以最少的查询次数（每次查询，可以选择一个位置，然后你能知道表中这个位置的数据），获知这个数是否在表中。 如果设计这个表为有序表，用二分法需要次查询。 有序表是最优的么？ 举一个例子，一个保存1，2，3里面的两个数的...
一个面试题，号称是微软的 输入，如何在O(n)的时间，用O(1)的空间，将这个序列顺序改为。 刚一眼看上去觉得很容易，做了一回儿才发现深不可测。题目大致是要求在线性时间，常数空间实现下面的置换 x -> 2x mod 2n+1 我做了两小时没做出来，上网一搜，最近这个题目很热，已经有人在讨论这个题目，还翻出了问题的发源地http://www.cs.uvic.ca/~jellis/perfect.html，一个完美洗牌的...
Tsinghua ITCS Theory Day (I) time: Apr. 11, 2:00-5:00pm The Institute for Theoretical Computer Science in Tsinghua University has initiated a Theory Day program, a one-day public workshop to be held each semester. This program is intended to communicate some of the exciting latest research results in theoretical computer science, especially those carried out in China. The [......
Princeton的Sanjeev Arora和Boaz Barak最近写了一本计算复杂性方面的书：Complexity Theory: A Modern Approach，其初稿提供下载，并承诺出版后也会继续保留——要是所有作者都这么好心就好了。 下面这段摘自于第二章NP and NP completeness，写得很有趣。为什么多数人不同意P=NP呢？因为 “if (3SAT has a O(n^2) algorithm), then this would have consequences of the greatest magnitude. That is to say, it would clearly indicate ...
Rob Pike, 最伟大的 C 语言大师之一 , 在Notes on C Programming(英文原文)中从另一个稍微不同的角度表述了 Unix 的哲学: 你无法断定程序会在什么地方耗费运行时间。瓶颈经常出现在想不到的地方，所以别急于胡乱找个地方改代码，除非你已经证实那儿就是瓶颈所在。 估量。在你没对代码进行估量，特别是没找到最耗时的那部分之前，别去优化速度。 花哨的算法在 n 很小时通常很...
Xie Xie给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。 所谓素数筛法就是那个求小于n的所有素数最简单的算法： bool* prime(int n) { bool *p = new bool[n]; memset(p, 0, sizeof p); for (int i = 2; i < n; i++) if (!p[i]) for (int j = 2*i; j < n; j+=i) p[j] = true; [...]
上篇文章扫雷是NP完全问题之后，You Xu提到＂不光扫雷是NP 完全问题，空当接龙问题也极有可能是一个NP完全问题。目前最好的通用 planner只能解半副牌＂。他说对了，不光扫雷，Windows自带的游戏都是NP完全的。Windows自带的游戏除了扫雷，还有空当接龙和蜘蛛纸牌。 空当接龙是NP完全问题 论文：Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal ...
本科时有同学扫雷最快可以在60多秒完成高级难度，让我这种最快130秒的人非常惭愧，当时就想着编一个全自动的扫雷程序，不过一直也没写。今天才知道，原来扫雷问题是NP完全的... 结果于2000年发表在Mathematical Intelligencer上，论文题目是Minesweeper is NP-complete，这里有作者的简单的问题和证明介绍。证明方法是证明扫雷问题可以编码任何逻辑电路，包括NP-hard的3SAT问题。作者还...
给定的实数矩阵，每行和每列都是递增的，求这个数的中位数。 使用类似Tarjan的线性中位数的方法，每次找每列中位数，然后找中位数的中位数，之后可以删除前一半列的上半部分或者后一半列的下半部分，这样可以实现复杂性。 但是这个问题是有的算法的，在Top Language Google Group的Obtuse Sword的指点下，找到了这个问题的原始论文：Generalized Selection and Ranking: Sorted Matrices。事...
ACM(美国计算机协会）在ICALP会议上宣布了2008年哥德尔（Gödel）奖由Dan Spielman和Shang-Hua Teng 获得。 滕尚华老师是清华大学计算机系前讲席教授组成员之一。在讲席教授组解散之后，滕老师也多次访问理论计算机研究中心。 哥德尔（Gödel）奖：以前对之了解不多。查了一下，是理论计算机界的一个大奖，每次都针对某个突破性结果，比如1999年获奖的Peter Shor的量子大数分解算法...
Xie Xie推荐了一本今年出版的一本新书，Encyclopedia of Algorithms，全书1200页，涵盖各类有名问题的算法，概率算法，近似算法，量子算法等。 翻了一下，很多算法都不是直接给出的，只是给出一些原理描述和参考文献。看来这本也真只能当当索引用了。 没事做的话可以先欣赏一下第698页的O(n)的平面图判定算法。 按照推荐人xiexie的说法，看在原书高达309欧元的价格份上，也得下...