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

作者: , 共 573 字

注 : 这个问题来自 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 即博弈论,目前在经济学中运用得最多 ( 纳什更因为他在这上面的工作拿到了诺贝尔经济学奖 )。但在最近几年,理论计算机界对它的研究也很热。
前面 已经提到了显示中大多数难解问题问题最后都被证明是 NP- 完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在 这篇文章 提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
相似度: 0.071
注:此游戏很有名,有同学问我其算法,我在网上找了一下,居然没多少中文资料,这里按照以前看过的一份答案回忆整理贴出。
编程 » 算法, 算法分析
下面这个求 \( 1/\sqrt{x}\) 的函数号称比直接调用 sqrt 库函数快 4 倍,来自游戏 Quake III 的源代码。
递归算法的复杂度通常很难衡量,一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大,如果我们可以保存每次子递归的结果的话,递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。