9
一个简单图的三染色算法问题
source link: https://zhiqiang.org/cs/3-color-a-simple-graph.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一个简单图的三染色算法问题
注: 这个问题来自China Theory Week 2008的 Open Problems Session。
我们知道在数学里证明一个东西的存在性的时候，有时候只证明了「存在性」，而且在证明过程中并没有说明如何找到它，这种证明方法被称为「非构造性证明」。有些流派的数学家对这种证明方法非常不满，具体这里就不详谈了。
这里要说的是，一个玩意儿，即时你知道它总是存在的，它也是可以算出来的，但是不是就一定能够很快的比如在多项式时间之内算出来呢？
Game Theory已经证明了在两人非合作博弈中，纳什均衡总是存在的，但是如何计算它确被证明是 PPAD-hard的，一个被猜测不属于 P 的复杂类。
纳什均衡的计算问题不太好理解，下面介绍一个问题，描述比较简单非常容易理解。它有类似的效果，存在性可在数学上被证明，但如何计算它却不知道，复杂性也未知。
输入：一个3n 点的图，顶点构成一个正3n 边形，以及它们之间的6n 条边。其中3n 条为多边形的边，另外3n 条边构成n 个顶点互不重合的三角形。下图为一个n=3 的例子。
输出：这个图的一种三染色方案（给定点染色，使任何有边相连的顶点都不同色）。
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK