是否有一個多項式時間算法來知道一組整數是否可以劃分爲兩個相等的總和？

Question

如果有的話，如果任何人都可以指引我，我會很高興。優選用於該目的的計算機程序。

我實際上指的是一個多項式時間算法，它只會測試（沒有實際的分割），如果一組整數可以分成兩個相等的總和。如果是的話，程序返回true，如果沒有返回false。

Answer 1

它是NP-Hard（也是NP-Complete）。

我的意思是我們還沒有找到一個多項式時間算法，而且我們還沒有證明這個算法不存在。 大家都相信沒有多項式時間算法存在，因爲我們已經嘗試了很多年。有很多這樣的問題，我們既沒有證明多項式時間算法的存在，也沒有證明存在多項式時間算法。

但事實證明，如果你證明或否定多項式時間算法的存在對於一個這樣的問題，這同樣適用於類的所有元素。