2

与えられたもの：

  • 約800個の疑似ランダム符号なし64ビット整数のセット。

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

  • 同じ種類のターゲット整数17358988457627394926。ほとんどの場合、セットには含まれていません。

セットの最大50（またはそれ以下）の整数のサブセットをXORすることにより、ターゲット整数が作成されたことが保証されます。

XORされたときにターゲット整数を作成する整数のサブセット（必ずしも最小ではない）を見つけるための最も効率的なアルゴリズムは何ですか？

NP困難の場合、それを証明するための基本的な考え方は何でしょうか。

4

1 に答える 1

5

Z 2で作業する場合、問題は行列方程式の解を見つけることと同じですAx = b。ここAで、は各要素の2値展開をとることによって形成される64x800の2値行列であり、bは解を表す64要素の2値行列です。

このようなシステムは、単純なガウスの消去法を使用して非常に簡単に解くことができます。

于 2012-10-07T00:09:09.307 に答える