将某些整数的xor设为零所需的最小总和

Question

这是一个处理算法和按位xor运算的问题.我们给出了x1*x2*x3*....*xn=P,其中star(*)操作表示XOR(按位)操作, x1到xn是正整数.P也是正整数.我们需要找到min(a1 + a2 + a3 + ..... an) 这样的关系成立 - > (x1+a1)*(x2+a2)*(x3+a3)*....*(xn+an)=0.'+'表示正常的加法操作.

Answer 1

重述为有界整数线性规划问题

该问题可以重述为以下有界 ILP（整数线性规划）问题。

Let x1,...,xN be as in the original problem, i.e. the goal is to minimize(a1+...+aN)
under the conditions (x1+a1) XOR ... (xN+aN) = 0, a1,...,aN >= 0.

The following is than an equivalent bounded ILP:
Find b[k,i] (0 <= k <= K, 1 <= i <= N) and s[k] (0 <= k <= K) such that
  (A) b[k,i] in {0, 1} for all i=1..n, k=0..K,
  (B) s[k] is an integer >= 0 for all k=0..K,
  (C) sum(b[k,i]*2^k, k=0..K) >= x[i] for all i = 1..N,
  (D) sum(b[k,i], i=1..N) = 2*s[k] for all k = 0..K
and minimize
  sum(b[k,i]*2^k, i=1..n, k=0..K).

From a solution of the bounded ILP the ai's are obtained by
  a[i] = sum(b[k,i]*2^k, k=0..(K-1)) - x[i]

b[k,i] 只是这里 (xi+ai) 的二进制表示的第 k 位（条件（A）和（C））。为了使整体 XOR 为零，对于每个 k，偶数个 b[k,i] 必须为 1。这由条件(B)和(D)表示。（请注意，(D) 中的左侧总和必须为偶数，即使它等于 2*s[k] 并且 s[k] 是整数）。

K，即表示所有(xi+ai)所需的位数（实际上是加1）必须事先确定。选择一个 K，使得所有 xi < 2^K 就足够了，即 ai 比最大的 xi 大一点。但选择更大的 K 并不重要，最高位将简单地显示为零。如果K选得太小，ILP将无解。

解的存在性

忽略极小条件，问题可以重述为

给定 x, yz，其中 x <= y，找到 a 和 b，使得 (x+a) XOR (y+b) = z

给定原始问题的一个实例，其中 N >= 2。设 x=x1, y=x2, z=(x3 XOR x4 XOR ... xn)。如果找到合适的a和b，则设a1=a，a2=b，a3=...=an=0，即可得到原问题的解。

简化的问题通过以下方式解决（再次忽略极小性）

1. 如果 (y XOR z) >= x 则 a: = ((y XOR z) - x), b := 0 是解 (*)
2. 如果 (x XOR z) >= y 则 a := 0, b := ((x XOR z) - y) 是解 (*)
3. 否则，选择一个 a 使得 (x+a) XOR z >= y。这样的 a 始终存在，例如，您可以让 a := 2^k 且 2^k > max(x,y,z)。设置 b := ((x+a) XOR z) - y) 得出解 (*)

(*) 要了解这些确实是解决方案，您只需应用一些代数即可。例如，在情况(1)中，将a和b代入后，得到：(x+(y XOR z)-x) XOR (y+0)。这与： (y XOR z) XOR y 相同，因此与： zqed 情况 (2) 的工作原理类似。在情况 (3) 中，您得到： (x+a) XOR (y+((x+a) XOR z)-y) = (x+a) XOR ((x+a) XOR z) = z。

这表明，对于 N >= 2，解总是存在。

我不知道这些解决方案是否是最小的。在情况(3)中，它显然取决于a的选择，所以至少你必须找出a的最佳选择。也可能是原始问题允许比简化问题更小的解决方案。不管怎样，也许这个重述可以帮助某人找出完整的解决方案。

顺便说一句，事实上，最初的问题本质上让你完全自由地选择如何将修正值 ai “分散”到 xi 上，这让我想知道这是否不等同于某种背包问题。如果是这样，找到一个最小的解决方案很可能是 NP 困难的。

关于极简性的观察

采取以下问题

(1+a1) XOR (3+a2) XOR (6+a3) = 0

用二进制表示，即

(001b+a1) XOR (011b+a2) XOR (110b+a3) = 0

a1=a2=a3=0 的余数为 001b XOR 011b XOR 110b = 100b。因此，一个明显的解决方案是a1=4，a2=0，a3=0。或者a1=0，a2=4，a3=0。不过这个解决方案并不是最小的 - 下面的解决方案更小

a1=1, a2=1, a3=0

它也是最小的，因为所有较小的解决方案只能有一个非零 ai，并且所有项 (2 XOR 3 XOR 6)、(1 XOR 4 XOR 6)、(1 XOR 3 XOR 7) 均为非零。

这表明从底部（即最低位）向上工作的格力算法不能工作，因为这样的算法会跳过前两位，因为它们的余数最初为零。

它还表明您无法从残数中选取某个非零位k并尝试通过将2^k添加到其中一个xi 来将其归零。有时您必须将其添加到多个 xi 中才能找到最小解决方案。

这让我更加相信找到最小解决方案是一个相对困难的问题。