这个问题是一个月前在Computational Complexity看到的.前两天在测不准原理还是不确定性原理我提到了不可证明问题,今天顺便把上面这个问题拿出来溜一溜.
这是一个非常非常自然的问题,看上去就是一个普通的组合问题,类似于 Ramsey 问题的变种,而且研究这个问题的(包括Erdos!)也多数是组合学家.但其答案却出人意料,因为这个问题被证明是不可证明的,它独立于 ZFC 公理体系:
定理:此命题成立当且仅当连续统假设不成立.
而连续统假设在上个世纪七十年代便已经证明了独立于 ZFC.
上面等价性定理的证明在这里(pdf ,英文).证明过程很短.即便我对集合论了解甚少,对我来说除了 Fact 1.3 之外,其余的都很好懂.
PS :做算法和复杂性的不要错过这个 blog :Computational Complexity.从 blog 标题就能看出它的内容了.
令人惊奇的是, blog 作者居然是北大中文系的.这位兄弟如此喜欢数学,完全可以向其前辈学习一下,从中文系转系到数学系去,这是有过先例的.
一个简单图的三染色算法问题 相似度: 0.172
Game Theory 即博弈论,目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖).但在最近几年,理论计算机界对它的研究也很热.