algorithm - 将一组整数中的哪些整数异或以生成目标整数？

Question

给出的是:

• 一组大约 800 个伪随机无符号 64 位整数。

  2910088619203924111,  8611579852607706360,  10743563285097812384,
  6712886796489718596, 17298387234720051377,  12467698534877227789,
  3782074590599432740,  1419307814092336225,   7951308495700413025,
  ...

• 同类的目标整数 17358988457627394926，在大多数情况下不在集合中。

可以保证目标整数是通过对集合中最多 50 个(或更少)整数的子集进行异或运算得到的。

什么是最有效的算法来找到一个整数的子集(任何，不一定是最小的)在异或时成为目标整数？

如果是 NP-hard，证明它的基本思路是什么？

Answer 1

在 Z₂ 中工作，该问题等同于找到矩阵方程 Ax = b 的解，其中 A 是 64x800对每个元素进行二元展开形成的二元矩阵，b是表示解的64元二元矩阵。

使用简单的高斯消元法很容易求解这样的系统。