In dem OrderedPartition
Problem besteht die Eingabe aus zwei Folgen von positiven ganzen Zahlen, und . Die Ausgabe ist eine Aufteilung der Indizes in zwei disjunkte Teilmengen und , so dass:
- Für alle und für alle : .
Mit anderen Worten, wir müssen zuerst die Indizes auf einer Linie so ordnen, dass die schwach ansteigen, und dann die Linie so schneiden, dass die Summe der auf beiden Seiten gleich ist.
Wenn alle sind, ist Bedingung 2 irrelevant und wir haben eine Instanz des NP-harten Problems. Wenn andererseits alle unterschiedlich sind, legt Bedingung 2 den Indizes eine einzige Reihenfolge auf, so dass nur Optionen zu überprüfen sind und das Problem polynomisch wird. Was passiert zwischen diesen Fällen?Partition
Um die Frage zu formalisieren, definieren Sie OrderedPartition[n,d]
für das Problem, das auf Instanzen der Größe , in denen die größte Teilmenge identischer Größe . Der einfache Fall, wenn alle -s unterschiedlich sind, ist und der schwierige Fall, wenn alle -s identisch sind, ist .OrderedPartition[n,1]
OrderedPartition[n,n]
Allgemeiner ist für jedes und in jedem Fall die Anzahl möglicher Partitionen, die die Bedingung 2 respektieren, . Wenn also , dann ist in immer noch ein Polynom .OrderedPartition[n,d]
OrderedPartition[n,d]
Andererseits können wir für jedes und von einem Problem mit ganzen Zahlen auf reduzieren . Sei eine Instanz von . Definieren Sie eine Instanz von:d p 1 , … , p dPartition
OrderedPartition[n,d]
Partition
OrderedPartition[n,d]
- Für jedes sei und .
- Für jedes sei und [wenn ungerade ist, mache so dass die Summe gerade ist] .n - d a n : = 2
Wenn also für eine ganze Zahl , dann ist NP-hart.OrderedPartition[n,d]
FRAGE: Was passiert in den Zwischenfällen, in denen superlogarithmisch, aber in ?
quelle