Soptq

Soptq

Probably a full-stack, mainly focusing on Distributed System / Consensus / Privacy-preserving Tech etc. Decentralization is a trend, privacy must be protected.
twitter
github
bilibili

tcs

cover

反馈边问题 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 同构…
cover
cover
cover
cover
cover

3 色问题的 NP-Complete 证明

3 色问题 (3-Color) 的描述如下:给定一个图 G,为 G 中每一个顶点涂色,要求每两个相邻的顶点颜色不一致。问是否可以用 3 种颜色完成上面的要求。 首先我们证明这个问题是 NP 问题。显然,若给定一个解,我们只需要遍历每一个节点,检查其与其相临节点的颜色是否一致…
cover
cover

顶点覆盖问题 NP-Complete 证明

顶点覆盖问题(Vertex Cover)的描述如下:给定 <G,k>,其中 G 是一个无向图,问图中是否存在点集 V,\lvert V \rvert <= k, 使得 V 中的每一个顶点覆盖 G 中所有的边。即 G 中每一条边的起点或终点都为 V 中的一个点。以下图为例,<A,B…
cover
cover
cover

分团问题 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…
ブログは、創作者によって署名され、ブロックチェーンに安全に保存されています。