Gibt es einen Polynomzeitalgorithmus, um zu wissen, ob eine Menge von ganzen Zahlen in zwei von gleicher Summe partitioniert werden kann?

Question

Wenn es welche gibt, wäre es mir eine große Freude, wenn mich irgendjemand zu irgendwas führen könnte. Bevorzugt mit einem Computerprogramm, das für diesen Zweck arbeitet.

Ich beziehe mich tatsächlich auf einen Polynomialzeitalgorithmus, der nur testen wird (ohne die tatsächliche Partitionierung), wenn eine Menge von ganzen Zahlen in zwei gleiche Summe partitioniert werden kann. Wie wenn ja, Programm zurückgeben wahr und wenn keine Rückkehr falsch.

Answer 1

Es ist NP-Hard (NP-Complete auch).

Was ich meine ist, dass wir nicht in der Lage waren, einen Polynomialzeitalgorithmus zu finden, und wir haben nicht bewiesen, dass man nicht existiert. Es wird von jedem geglaubt, dass kein polynomialer Zeitalgorithmus existiert, da wir viel über Jahre versucht haben. Es gibt viele solche NP-Complete Probleme, für die wir weder die Existenz des Polynomialzeitalgorithmus bewiesen noch die Existenz von Eins widerlegt haben.

Aber es stellt sich heraus, dass, wenn Sie die Existenz des Polynomialzeitalgorithmus für ein solches Problem beweisen oder widerlegen, das gleiche gilt für alle Elemente der Klasse NP-Complete.