The Partition Problem, and How The Distribution of Input Bits Affects the Solving Process
Nikita Sazhinov, Ruben Horn, Pieter Adriaans, Daan van den Berg · 2023
The hardness of the partition problem does not only depend on the number of integers in the problem instance, but also on their magnitude, measured in informational bits. In this work, we will show that also the exact distribution of informational bits among the integers influences the hardness for at least one exact and three heuristic algorithms.