Computational Hardness of Random CNP Instances

This article explores the computational hardness of random Cardinality Number Partitioning (CNP) problems, focusing on phase transitions between “hard” and “perfect” solution regions. Using the complete differencing algorithm, the study shows how problem size and bias influence difficulty, with average hardness peaking near phase transitions. The findings suggest that biased CNP instances remain computationally challenging, making them strong benchmark candidates for testing SPIM hardware efficiency in solving complex optimization tasks.