子集和问题

证明：-

1. 子集和
2. 顶点覆盖≤ρ子集覆盖
3. 子集覆盖≤ρ顶点覆盖
4. 子集和ϵ NP

1）子集和

定义：-为获得并集而获得完整图形G的所有边之后的边子集数, 这称为子集覆盖。

根据图G, 你已经创建了Subset Cover = 2的大小

v1{e1, e6}     v2{e5, e2}     v3{e2, e4, e6}     v4{e1, e3, e5}     v5{e4}     v6{e3}
v3Uv4= {e1, e2, e3, e4, e5, e6} complete set of edges after the union of vertices.

2）顶点覆盖≤ρ子集覆盖

在顶点N的图形G中, 如果存在大小为k的顶点覆盖, 则还必须存在大小为k的子集覆盖。如果你可以在多项式时间内从“顶点覆盖”减少为“子集覆盖”, 则表示你做对了。

3）子集覆盖≤ρ顶点覆盖

仅为了验证输出, 执行约简并创建Clique, 并且通过方程式, N-K也会验证Clique, 并且通过Clique你可以快速生成3CNF, 并在多项式时间内求解3CNF的布尔函数。你将获得输出。这表示输出已通过验证。

4）子机盖ϵ NP：-

证明：-如你所知, 你可以通过“顶点覆盖”获得子集覆盖, 并通过“派系”获得“顶点覆盖”, 并将基于决策的NP问题转换为“派系”, 首先必须将3CNF和3CNF转换为SAT, 然后将SAT转换为CIRCUIT SAT来自NP。

NPC证明：

已成功在多项式时间内从“顶点覆盖到子集覆盖”进行了约简

正如你在上述对话中所做的那样, 还已在多项式时间内验证了输出, 因此得出结论, SUBSET COVER也来自NPC。

独立套装

图G =（V, E）的独立集合是顶点的子集V’⊆V, 这样E中的每个边都入​​射到V中的一个顶点上。独立集问题是在G中找到最大的独立集。找到小型独立集并不难, 例如, 小型独立集是一个单独的节点, 但是很难找到大型独立集。