哪些整數從一組整數到XOR來製作一個目標整數？

一組約800僞隨機64位無符號整數。

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

一個目標整數同類17358988457627394926，在大多數情況下不在集合。

這是保證目標整數是由異或所述一組多達50個（或更少）的整數的子集在一起而製成。

什麼是最有效的算法來找到一個子集（任何，而不是最小的）的整數，使XORed時的目標整數？

如果NP-hard，證明它的基本思想是什麼？

來源

2012-10-06 Niklas

我收回了我的最後一條評論......如果你想要的只是一個解決方案（不是最好的解決方案），它不是NP難的。 – nneonneo

@nneonneo：謝謝。我在問題中澄清說，任何解決方案都足夠了。 – Niklas

這個問題與加密有關嗎？你能否提供一個例子，說明如何以及爲什麼你需要通過一個數組中的一組值對xor操作的結果賦予目標整數。你有關於如何應用高斯消去解決這個問題的想法嗎？ –

Z中工作，問題是等效於尋找解決矩陣方程Ax = b，其中A是通過取每個元素和b的二進制展開形成的64x800二進制矩陣是64元件二進制矩陣代表解決方案。

這樣的系統很容易使用直接的高斯消元來解決。

來源

2012-10-07 00:09:09 nneonneo

非常感謝。（{0，1}，XOR）形成一個組是一個簡單而強大的洞察力。 – Niklas

哪些整數從一組整數到XOR來製作一個目標整數？

回答

相關問題