Algorithmic obstructions in the random number partitioning problem

We consider the algorithmic problem of finding a near-optimal solution for the number partitioning problem (NPP). This problem appears in many practical applications, including the design of randomized controlled trials, multiprocessor scheduling, and cryptography. It is also of theoretical significance. The NPP possesses a so-called statistical-to-computational gap: when its input X has distribution N(0, In), the optimal value of the NPP is Θ ( √ n2-n) w.h.p., whereas the best-known polynomial-time algorithm achieves an objective value of only 2-Θ (log2 n) w.h.p. In this paper we initiate the study of the nature of this gap. Inspired by insights from statistical physics, we study the landscape of the NPP and establish the presence of the overlap gap property (OGP), an intricate geometrical property which is known to be a rigorous evidence of an algorithmic hardness for large classes of algorithms. By leveraging the OGP, we establish that: (a) any sufficiently stable algorithm, appropriately defined, fails to find a near-optimal solution with energy below 2-ω(nlog-1/5 n), and (b) a very natural Markov chain Monte Carlo dynamic fails to find near-optimal solutions. Our simulation results suggest that the state-of-the-art algorithm achieving the value of 2-Θ (log2 n) is indeed stable, but formally verifying this is left as an open problem. OGP regards the overlap structure of m-tuples of solutions achieving a certain objective value. When m is constant, we prove the presence of OGP for the objective values of order 2-Θ(n) and the absence of it in the regime 2-o(n). Interestingly though, by considering overlaps with growing values of m, we prove the presence of the OGP up to the level 2-ω( √ n log n). Our proof of the failure of stable algorithms at values 2-ω(nlog-1/5 n) employs methods from Ramsey theory from the extremal combinatorics and is of independent interest.