广义划分问题（GPAR）

广义划分问题（GPAR）对划分问题的子集条件作出了限制，要求划分出的两个子集之间是 2倍 的关系，而不是相等，即：

$\sum_{a \in a^{\prime}} S(a)= \textcolor{red}{2}\sum_{a \in A-A^{\prime}} S(a)$

该问题通过将划分问题（PAR）归约到 GPAR 来证明。

NPC 证明

令划分问题实例 $A=\{a1,a2,...,an\}$ ，令 $B=S(A)/2$，$S(A)=\sum_{a\in A}S(a)$。

构建广义划分实例 $B=A \cup \{S(A),2S(A)+B\}$。

添加两个元素为常数项时间，所以该变换在多项式时间内可得。

(->) 当 PAR 存在划分 $A'$ 的时候，可得$S(A')=S(A-A')=B$，此时 $2S(A)+B+S(A') = 2(S(A)+B)$，得证

(<-) 当 GPAR 存在划分时候， 因为

$S(A)+2S(A)+B=3S(A)+B>2S(A)$

所以GPAR 问题中新增的两个元素 $\{S(A),2S(A)+B\}$ 不可能同时在一个划分子集中，一定分别在两个子集中。

此时，必定存在一个从原 $A$ 中挑选出子集 $A'$，，使得下式成立（GPAR的划分条件）：

$2S(A)+B+S(A')=2(S(A)+S(A-A'))$

对上式代入 $S(A')=S(A)-S(A-A')$，以此解得

$S(A')=S(A-A')=B$

ps1： 构建元素时是否可以构建 $\{S(A)-B,2S(A)-B\}$？答案是不可以，因为此时存在划分的话，这两个元素可能会在一个子集中。

ps2： 可以通过该方法证明任意倍数的广义划分问题。

该证明缺少了一步分情况讨论的步骤，具体请参考issue#12