0%

X3C-1与广义划分问题的NP完全性证明


老师上课留的作业

还蛮简单的(


X3C-1问题

首先你需要知道什么是X3C问题(假装你知道了,其实是我懒得写了

X3C-1问题是任意两个元素的交的大小小于等于1

证明

我们尝试用X3C来归约到X3C-1来证明这件事情。

其实蛮简单的,假设$(a,b,c)$是X3C集合的一个元素。

我们把它拆成以下5个元素

$$(a, e1, e2) \ (b, e3, e4) \ (c, e5, e6) \ (e1, e3, e5) \ (e2, e4, e6)$$

正确性显然(

广义划分问题

狭义的划分问题是将集合里的元素划分成两个部分,每个部分的和相等

而广义划分问题便是使得两个部分保持1:2的关系

证明

尝试从划分问题归约到这个问题。

假设原集合为S

加入$\frac{3}{2}S$与$\frac{7}{2}S$两个元素,正确性显然(

abab