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

zhiqiang9月 25, 2008 计算机科学

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

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

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

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

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

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

输出：这个图的一种三染色方案（给定点染色，使任何有边相连的顶点都不同色）。

你可能感兴趣的

阅微堂