We now illustrate the OGP and its variants for the Number Partitioning problem and the maximum clique problem as examples.
The discussion will be informal and references containing detailed derivations will be provided.
The instance
\(\xi \)  of the Number Partitioning problem is a sequence \(X_1,\ldots ,X_N\)  of independent standard normal random variables.
For every binary vector \(\sigma \in \lbrace -1,1\rbrace ^N\) , the inner product \(Z(\sigma )=\langle \xi , \sigma \rangle \) 
is a mean zero normal random variable
with variance \(N\) . The likelihood that \(Z(\sigma )\)  takes value in an interval around zero with length
\(\sqrt{N}2^{-N}\)  is roughly \((2\pi )^{-{1\over 2}}\)  times the length of the interval, namely times \(2^{-N}\) . Thus the expected
number of such vectors \(\sigma \)  is of constant order \((2\pi )^{-{1\over 2}}\) 
since there are \(2^N\)  choices for \(\sigma \) . This gives
an intuition for why there do exist vectors achieving value \(\sqrt{N}2^{-N}\) . Details can be found
in [1]}. Any choice of order magnitude smaller
length interval leads to expectation converging to zero and thus
non-achievable with overwhelming probability. Now, to discuss the OGP,
fix constants \(\alpha ,\rho \in (0,1)\)  and consider pairs of
vectors \(\sigma ,\tau \)  which achieve objective value \(\sqrt{N}2^{-\alpha N}\) 
and have the scaled inner product \(N^{-1}\langle \sigma ,\tau \rangle =\rho \) . The expected number of such pairs is roughly
\({N\atopwithdelims (){1-\rho \over 2} N}\)  times the area of the square with side length approximately \(2^{-\alpha N}\) , namely
\(2^{-2\alpha N}\) . This is because
the likelihood that a pair of correlated gaussians \(Z(\sigma ),Z(\tau )\)  falls into a very small square around zero is dominated
by the area of this square up to a constant.
Approximating \({N\atopwithdelims (){1-\rho \over 2} N}\)  as \(\exp \left(N H({1-\rho \over 2})\right)\) , where
\(H(x)=-x\log x-(1-x)\log (1-x)\)  is the standard binary entropy, the expectation of the number of such pairs evaluates
to roughly
\(\exp \left(N\left(H({1-\rho \over 2})-2\alpha \log 2 \right)\right)\) . As the largest value of \(H(\cdot )\)  is \(\log 2\) , we obtain
an important discovery: for every \(\alpha \in (1/2,1)\) 
there is a region of \(\rho \)  of the form \((\rho _0,1)\)  for which the expectation
is exponentially small in \(N\) , and thus the value \(\sqrt{N}2^{-\alpha N}\)  is not achievable
by pairs of partitions \(\sigma \)  and \(\tau \)  with scaled inner products in \((\rho _0,1)\) ,
with
overwhelming probability. Specifically, for every pair of \(\mu \) -optimal
solutions \(\sigma ,\tau \)  with \(\mu =(2^{-\alpha N}-2^{-N})\) ,
it is the case that \(N^{-1}\langle \sigma ,\tau \rangle \)  is either 1
or at most \(\rho _0\) . With this value of \(\mu \)  and \(\nu _1=0,\nu _2=N(1-\rho _0)/2\) , we conclude that the model exhibits the OGP.
