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. Es ist möglicherweise "das einfachste schwere Problem".