Subset-Sum (Teilmengensumme) ist ein klassisches Entscheidungsproblem: Gegeben eine Liste von Zahlen und eine Zielsumme S — existiert eine Teilmenge, deren Summe exakt S ergibt? Auch wenn es trivial klingt, ist Subset-Sum NP-vollständig und einer der 21 Grund-Probleme aus Karps berühmter Liste von 1972. Praktisch lösbar wird es durch einen cleveren dynamischen Programmierungs-Ansatz, der allerdings „nur“ pseudo-polynomial ist.
Das Problem
Gegeben sind n Zahlen a₁, a₂, …, aₙ und eine Zielsumme S. Gesucht ist eine Teilmenge mit Summe genau S — jedes Element darf höchstens einmal verwendet werden. Ein Spezialfall ist die Partitionierung: Lässt sich die Liste in zwei Hälften mit gleicher Summe teilen? Subset-Sum ist außerdem ein Spezialfall des Rucksackproblems: Man setzt Werte und Gewichte gleich und die Kapazität auf S.
Warum ist es schwer?
Naiv probiert man 2ⁿ Teilmengen durch — bei 60 Zahlen sind das mehr als die Atome im sichtbaren Universum. Die Entscheidungsfrage ist NP-vollständig: Subset-Sum ist also mindestens so schwer wie SAT und alle anderen NP-Probleme. Auf dem Weg dorthin lässt sich etwa Graphfärbung auf Subset-Sum reduzieren.
Die DP-Lösung: pseudo-polynomial
Mit dynamischer Programmierung baut man ein boolesches Array dp[0…S]: dp[j] ist wahr, wenn die Summe j mit einer Teilmenge erreichbar ist. Für jede Zahl a aktualisiert man das Array rückwärts: dp[j] = dp[j] oder dp[j−a]. Das kostet O(n · S) Zeit und O(S) Speicher. Entscheidend ist die Feinheit: S ist ein Zahlenwert, keine Bitlänge. Verdoppelt man S, verdoppelt sich die Laufzeit — daher heißt das Verfahren „pseudo-polynomial“. Für kleine Zielsummen ist es extrem schnell, für riesige S (etwa mit 100 Stellen) nutzlos.
Approximation
Subset-Sum besitzt ein FPTAS (voll polynomielles Approximationsschema): Durch Skalieren und Runden der Zahlen erreicht ein Greedy-ähnlicher Ablauf in Polynomzeit eine beliebig gute Näherung (1−ε). Für die Variante „möglichst nahe an S“ liefert außerdem der Approximationsalgorithmus gute Garantien. Als ganzzahliges Programm (ILP) schreibt man es als Summe aᵢ·xᵢ = S mit Binärvariablen xᵢ.
Praxis
- Budget- und Rechnungsausgleich: Welche Posten ergeben exakt einen Zielbetrag?
- Lastverteilung: Aufträge auf Maschinen verteilen, sodass die Lasten möglichst gleich sind (Partitionierung).
- Kryptographie: Das Merkle-Hellman-Kryptosystem basierte auf Subset-Sum und wurde 1982 mit einer FPTAS-ähnlichen Attacke gebrochen — ein Lehrstück, warum NP-Schwere allein keine Sicherheit garantiert.
- Baustein in Zahlungs-, Scheduling- und Kombinatorik-Verfahren.
Verwandte Themen: Rucksackproblem, Dynamische Programmierung, Max-Flow-Min-Cut.