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…
此博客数据所有权由区块链加密技术和智能合约保障仅归创作者所有。