  We consider the algorithmic problem of finding a near-optimal solution for
the number partitioning problem (NPP). The NPP appears in many applications,
including the design of randomized controlled trials, multiprocessor
scheduling, and cryptography; and is also of theoretical significance. It
possesses a so-called statistical-to-computational gap: when its input $X$ has
distribution $\mathcal{N}(0,I_n)$, its optimal value is
$\Theta(\sqrt{n}2^{-n})$ w.h.p.; whereas the best polynomial-time algorithm
achieves an objective value of only $2^{-\Theta(\log^2 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 NPP and establish
the presence of the Overlap Gap Property (OGP), an intricate geometric 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^{-\omega(n \log^{-1/5} n)}$; and (b)
a very natural MCMC dynamics fails to find near-optimal solutions. Our
simulations suggest that the state of the art algorithm achieving
$2^{-\Theta(\log^2 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 in
the regime $2^{-\Theta(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^{-\omega(\sqrt{n\log n})}$.
Our proof of the failure of stable algorithms at values $2^{-\omega(n
\log^{-1/5} n)}$ employs methods from Ramsey Theory from the extremal
combinatorics, and is of independent interest.
