通俗得讲就是在一个简单有向图中存在一个顶点,走至多两步能达到的顶点数至少为走一步能达到的顶点数的 2 倍.
 注:简单有向图指任两点之间至多一条边.
 看上去蛮简单的,事实上很不好做,是一个 OPEN 多年的问题 ...
 Q. E. D.
 今天香港中文大学的 Prof. Cai 给我们上 graph algorithm.第一节课上教我们玩魔方,先给每人发了一个.我喜欢这样的教学方法 :) .
 利用线性代数可以给某些问题很精妙的证明, Matrix67 就给出了一个这样的例子 ,这也让我想起以前看见的另外一个例子,分享如下:
 这个题目听说是 MSRA 的面试题.
 在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛.规则呢,是这样.我们有 n 个人,作为一个小组来参加游戏.游戏中,主持人会给我们每人头上戴一顶帽子.帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的.小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色.每个游戏成员都被要求回答自己帽子的颜色.我们各人面前有三个按钮,可以选择"黑色""白色"或"弃权"( 也就是 pass ,不作猜测的意思 ).小组成员彼此之间没有任何信息交流,他们必须各自独立地作出自己的选择,并且谁也不知道其他人的选择.如果小组成员全部选择了 pass ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输.只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖.
 "杀人",英文名为 "Mafia Game",广泛流传于国内外.上个星期我们在玩的时候被 Elchanan Mossel 发现,然后他给了一个 talk ,内容就是杀人的理论分析.
 很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题.但如果这里的"更难"指得是解决问题所花费时间更长的话,这个论断是不正确的.从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的.
 80后,科学青年;宅居动物;
 习惯用Google获取信息;喜欢解决问题;