tcs
反馈边问题 NP-Complete 证明
反馈边 （Feedback Arc Set）问题的描述如下。给定一个有向图 G，问是否可以移除小于等于 k 条边使得 G 中没有循环。首先这个问题显然是 NP 问题。即给定移除的 k 条边，我只需要先把这 k 条边移除，然后判断剩下的图中是否有循环就可以了…
子图同构问题 NP-Complete 证明
子图同构（Subgraph isomorphism problem）问题的描述如下：给定两个图 G_1 和 G_2，判断 G_1 是否与 G_2 的一个子图同构。首先假如我们得到了 G_1，G_2 和对应的解（即 G_2 的子图 G_s 使得 G_s 与 G_1 同构…
3 色问题的 NP-Complete 证明
3 色问题 (3-Color) 的描述如下：给定一个图 G，为 G 中每一个顶点涂色，要求每两个相邻的顶点颜色不一致。问是否可以用 3 种颜色完成上面的要求。 首先我们证明这个问题是 NP 问题。显然，若给定一个解，我们只需要遍历每一个节点，检查其与其相临节点的颜色是否一致…
顶点覆盖问题 NP-Complete 证明
顶点覆盖问题（Vertex Cover）的描述如下：给定 <G,k>，其中 G 是一个无向图，问图中是否存在点集 V，\lvert V \rvert <= k， 使得 V 中的每一个顶点覆盖 G 中所有的边。即 G 中每一条边的起点或终点都为 V 中的一个点。以下图为例，<A,B…
分团问题 NP-Complete 证明
分团问题（Clique Problem） 的描述如下：给定 <G, k>，其中 G 是一个无向图，问图中是否存在点集 V 组成一个团，且 \lvert V \rvert <= k。即 V 中的点相互连接？以下图为例。<B,C,D,E> 就是符合条件的一个点集，因为这四个点相互连接…
3-SAT NP-Complete 证明
阅读本篇需要先理解 SAT 问题是 NP 完全的，其主要由 Cook–Levin theorem 证明。有很多非常优秀的资源都对 SAT 的 NP 完全性作了证明，但这里就先省略掉了，还请读者自己参考。以后有时间的话我会补一个我理解的 SAT 证明问题。 **3-SAT (3…