The Planted Number Partitioning Problem

Given a list of numbers X ∼ N (0, I_n ), the random number partitioning problem (NPP) seeks a partition σ ∈ {−1, 1}ⁿ with a small H(σ) = √¹_n|⟨σ, X⟩|. Being a worst-case NP-hard problem, it appears among the six ‘basic’ NP-complete problems by Garey and Johnson (1990) and exhibits rich features, including a rigorous phase transition (Mertens, 1998; Borgs et al., 2001). It is closely related to certain models in statistical mechanics (Bauke and Mertens, 2004; Borgs et al., 2009a,b), discrepancy minimization (Spencer, 1985; Matousek, 1999; Chazelle, 2000), and the design of randomized controlled trials in statistics (Harshaw et al., 2019). Additionally, the NPP exhibits a statistical-computational gap between the optimal value (Karmarkar et al., 1986) and the best known polynomial-time algorithms (Karmarkar and Karp, 1982; Yakir, 1996); recent work by Gamarnik and Kızıldağ (2023) established algorithmic barriers for the NPP. In this paper, we introduce a planted version of the random NPP: fix a σ^∗ ∈ {−1, 1}ⁿ and generate X ∼ N (0, I_n ) conditional on the event H(σ^∗ ) ≤ 3⁻ⁿ . The random and planted models are statistically distinguishable, since in the former case min_σ H(σ) = Θ(^√n2⁻ⁿ ) w.h.p. We first analyze the values of H(σ). We show that, perhaps surprisingly, planting does not induce partitions with objective values substantially smaller than 2⁻ⁿ: we have min_σ≠±σ ∗ H(σ) = ˜Θ(2⁻ⁿ ) w.h.p. Moreover, we precisely characterize the minimal H(σ) achievable at any fixed distance from σ^∗ . Specifically, we establish that for any ρ ∈ (0, 1), min^{H(σ) = ˜}Θ⁽2^−nhb(ρ)⁾, σ:d_H (σ,σ^∗ )=ρn w.h.p. under the planted measure, where h_b (·) is the binary entropy function (logarithm base 2). 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) . Stable algorithms are those for which a small perturbation of its inputs leads to only a small change in its output—namely, the returned partition. Numerous powerful algorithmic frameworks exhibit such an input-stability. 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.