一个简单图的三染色算法问题

作者: , 共 536 字

注: 这个问题来自China Theory Week 2008的 Open Problems Session。

我们知道在数学里证明一个东西的存在性的时候,有时候只证明了「存在性」,而且在证明过程中并没有说明如何找到它,这种证明方法被称为「非构造性证明」。有些流派的数学家对这种证明方法非常不满,具体这里就不详谈了。

这里要说的是,一个玩意儿,即时你知道它总是存在的,它也是可以算出来的,但是不是就一定能够很快的比如在多项式时间之内算出来呢?

Game Theory已经证明了在两人非合作博弈中,纳什均衡总是存在的,但是如何计算它确被证明是 PPAD-hard的,一个被猜测不属于 P 的复杂类。

纳什均衡的计算问题不太好理解,下面介绍一个问题,描述比较简单非常容易理解。它有类似的效果,存在性可在数学上被证明,但如何计算它却不知道,复杂性也未知。

输入:一个\( 3n\) 点的图,顶点构成一个正\( 3n\) 边形,以及它们之间的\( 6n\) 条边。其中\( 3n\) 条为多边形的边,另外\( 3n\) 条边构成\( n\) 个顶点互不重合的三角形。下图为一个\( n=3\) 的例子。

三染色示例

输出:这个图的一种三染色方案(给定点染色,使任何有边相连的顶点都不同色)。

Q. E. D.

类似文章:
命题:实数集\( \mathcal{R}\) 上的任何一个可数种颜色染色方案,都存在四个不等的同色点\( x, y, z, w\) 使得\( x+y=z+w\)
Game Theory 即博弈论,目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年,理论计算机界对它的研究也很热。
相似度: 0.072
注:此游戏很有名,有同学问我其算法,我在网上找了一下,居然没多少中文资料,这里按照以前看过的一份答案回忆整理贴出。
前面已经提到了显示中大多数难解问题问题最后都被证明是 NP-完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在这篇文章提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
相似度: 0.070
Alice 和 Bob 两人玩一种硬币游戏。游戏在一个\( 2\times2\) 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是Andrew Yao的研究方向
数学 » open问题, 图论
孙博告诉我的,求证
相似度: 0.065
今天香港中文大学的Prof. Cai给我们上 graph algorithm。第一节课上教我们玩魔方,先给每人发了一个。我喜欢这样的教学方法 :) 。
编程 » 算法, 算法分析
下面这个求\( 1/\sqrt{x}\) 的函数号称比直接调用 sqrt 库函数快 4 倍,来自游戏 Quake III 的源代码。
递归算法的复杂度通常很难衡量,一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大,如果我们可以保存每次子递归的结果的话,递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。