Partitionsproblem mit unterschiedlichen Ganzzahlen

8

Das Partitionsproblem ist ein bekanntes NP-vollständiges Problem. In den Definitionen, die ich gesehen habe, wird angenommen, dass die Eingabe eine Mehrfachmenge von Ganzzahlen ist, und wir möchten die Existenz einer Partition in zwei Mengen mit derselben Summe entscheiden. Meine Frage ist:

Ist das Partitionsproblem immer noch NP-vollständig, wenn alle Eingabe-Ganzzahlen unterschiedlich sind (dh keine Ganzzahl wird wiederholt)?

Mohammad Al-Turkistany
quelle

Antworten:

13

Hier ist ein Überblick über eine Reduzierung von PARTITION auf UNIQUE PARTITION. Angenommen, die ursprünglichen Nummern sindx1,,xn und das Ziel ist T. Ich nehme das alles anxisind positive ganze Zahlen. Die neuen Zahlen werden sein2nxi+i, ebenso gut wie 1,2,4,,2n/2und das neue Ziel ist 2nT+2n/2. (Die Zahlen2n,2n/2 sind ziemlich willkürlich und könnten viel kleiner gemacht werden.)

Yuval Filmus
quelle
Übrigens, ist eine eindeutige Partition im starken Sinne NP-hart?. Hier möchte ich entscheiden, ob das Problem der Eingabe in die Partition eine eindeutige Lösung hat.
Mohammad Al-Turkistany
Das klingt nach einer ganz anderen Frage.
Yuval Filmus
Ok, ich werde es als separate Frage posten.
Mohammad Al-Turkistany