Partitionierungsproblem
Das Partitionierungsproblem ist ein mathematisches Problem, das durch seine NP-Schwere eine große Bedeutung in der Informatik erlangt hat. Es beschäftigt sich damit, einen Algorithmus zu finden, mit dem für eine beliebige natürliche Zahl alle möglichen Darstellungen als Summe von natürlichen Zahlen (die Zahlpartitionen der Ausgangszahl) bestimmt werden können.
→ Die Anzahl der Darstellungen einer natürlichen Zahl als Summe von natürlichen Zahlen wird als Wert der Partitionsfunktion von definiert. Formeln zur Berechnung der Partitionsfunktion und mathematische Anwendungen der Zahlpartitionen werden im Artikel Partitionsfunktion beschrieben. Der vorliegende Artikel beschreibt die Fragestellung als Problem der theoretischen Informatik und Komplexitätstheorie und Anwendungen der Zahlpartitionen auf Probleme in Informatik und Technik.
