Abstract
Given a list X∼𝒩(0,I_n) of numbers, the random number partitioning problem (NPP) seeks a partition σ∈ -1,1^n with a small H(σ)=1/√(n)|⟨σ,X⟩|. The NPP has been extensively studied in computer science, probability and combinatorics; it is also closely linked to covariate balancing and randomized controlled trials. We introduce a planted version of the random NPP: fix a σ* and generate X∼𝒩(0,I_n) conditional on H(σ^*)≤ 3^-n. The random and planted models are statistically distinguishable, since in the former case min_σH(σ)=Θ(√(n)2^-n) w.h.p. We first analyze the values of H(σ). We show that, perhaps surprisingly, planting does not yield partitions with objective values substantially smaller than 2^-n: we have min_σ±σ* H(σ) = Θ(2^-n) w.h.p. Moreover, we precisely characterize the minimal H(σ) achievable at any fixed distance from σ^*. Turning to the algorithmic problem, we ask whether one can efficiently find a partition σ with small H(σ). We prove that planted NPP exhibits the multi Overlap Gap Property (m-OGP) at scales 2^-Θ(n). Building on this barrier, we show that stable algorithms satisfying a natural anti-concentration property cannot find partitions with H(σ)=2^-Θ(n). This is the first instance where the m-OGP rules out stable algorithms in a planted setting. Our results demonstrate that the multi OGP framework, previously developed for unplanted models, extends naturally to planted ones when the goal is to recover low-objective solutions. They further point to a statistical–computational gap: although the random and planted NPP are statistically distinguishable, we conjecture that no polynomial-time algorithm can distinguish them with nontrivial advantage. Our results demonstrate that planted NPP harbors intriguing features and it is a particularly promising model for probing algorithmic barriers in planted problems.