We now introduce the Overlap Gap Property (abbreviated as OGP) and its several variants.
The term was introduced in [1]},
but the property itself was discovered by
Achlioptas and Ricci-Tersenghi [2]}, and
Mezard, Mora and Zecchina [3]}.
The definition of the OGP pertains to a particular
instance \(\xi \)  of the randomness \(\Xi _N\) . We say that the optimization
problem \(\min _\sigma \mathcal {L}(\sigma ,\xi )\)  exhibits the OGP with values
\(\mu >0, 0\le \nu _1<\nu _2\)  if for every two solutions \(\sigma ,\tau \)  which are \(\mu \) -optimal in the
additive sense, namely satisfy
\(\mathcal {L}(\sigma ,\xi )\le c^*+\mu ,\mathcal {L}(\tau ,\xi )\le c^*+\mu \) , it is the case that
either \(\rho _N(\sigma ,\tau )\le \nu _1\)  or
\(\rho _N(\sigma ,\tau )\ge \nu _2\) . Intuitively, the definition says that every two solutions
which are ”close” (within an additive error \(\mu \) )
to optimality, are either ”close” (at most distance \(\nu _1\) ) to each other,
or ”far” (at least distance \(\nu _2\) ) from each other,
thus exhibiting a fundamental topological discontinuity of the set of distances
of near optimal solutions. In the case
of random instances \(\Xi _N\)  we say the the problem exhibits the OGP
if the problem \(\min \mathcal {L}(\sigma ,\xi )\)  exhibits the OGP
with high likelihood when \(\xi \)  is generated according to the law \(\Xi _N\) .
An illustration of the OGP is depicted on Figure REF .
The notion of the ”overlap” refers to the fact that distances in
normed space are directly relatable to inner products, commonly called overlaps
in the spin glass theory, via \(\Vert \sigma -\tau \Vert _2^2=\Vert \sigma \Vert _2^2+\Vert \tau \Vert _2^2-2\langle \sigma ,\tau \rangle \) ,
and the fact that solutions \(\sigma ,\tau \) 
themselves often have identical or close to identical norms. The OGP is of interest only for
certain choices of parameters \(\mu ,\nu _1,\nu _2\)  which is
always problem dependent. Furthermore, all of these parameters along with the optimal
value \(c^*\)  are usually dependent on the problem size, such as the number of Boolean variables
in the K-SAT model or number of nodes in a graph.
In particular, the property is of interest only if there are
pairs of \(\mu \) -optimal solutions \(\sigma ,\tau \) 
satisfying both \(\rho _N(\sigma ,\tau )\le \nu _1\)  and \(\rho _N(\sigma ,\tau )\ge \nu _2\)  property.
The first case is trivial as we can take \(\tau =\sigma \) ,
but the existence of pairs with distance at least \(\nu _2\)  needs to be verified.
Establishing the OGP rigorously can be either straightforward or technically very involved,
again depending on the problem.
It is should not be surprising that the presence of the OGP presents a potential difficulty
in finding an optimal solution, due to the presence of
multiple local minima, similarly to the lack of convexity property.
An important distinction should be noted, however, between the OGP and the lack of
convexity property. The function \(\mathcal {L}(\sigma ,\xi )\) 
can be non-convex, but not exhibiting the OGP, as depicted on Figure REF .
Thus the ”common” intractability obstruction presented by
non-convexity is not identical with the OGP. Also, the solution space \(\Sigma _N\)  is
often discrete (such as the binary cube) rendering the notions
of convexity non-applicable.
<FIGURE>