姜咏江

计算机科学的一些题目长期得不到很好地解决，问题可能出现在数据结构上。依据SAT子句的概念，我构造了图的0和1 表示方法。进而使一些图的难题解答起来十分容易。例如图的最小顶点覆盖问题，容易得连我自己都无法相信了。反复考证，我确信是对的。今天写了个英文paper放到arXiv上，让那些所谓的内行去评价吧。

顶点覆盖的中心思想非常简单：由高到低删除关联度高的顶点和它连接的边，当剩下的顶点都无边相连的时侯，删去的那些顶点就是最小顶点覆盖。

我把这一切都变成了对二维表操作，每一个元素对二维表的访问时间复杂度为O(n²)，n个元素的访问自然不超过O(n³)。

对图用0和1的表示，一般只有所谓邻接矩阵，怎么就没想到关联度表示方法呢？我构造的关联度表示的图数据结构，极易实现对顶点覆盖、图同构等问题的求解。还有团之类的一些问题我有时间整理一下，再告诉朋友们。

SAT问题、顶点覆盖问题、图同构问题、哈密顿回路问题、TSP等我相信都可以在多项式时间内求出准确解。让我们一起努力吧。

2017-1-8