Finally, we say that a family of instances \(\Xi \) 
satisfies the m-OGP with parameters \(\mu ,\nu _1<\nu _2\)  and \(m\) , if for every \(m\) -collection of instances
\(\xi _1,\ldots ,\xi _m\in \Xi \)  and every collection
of solutions \(\sigma _1,\ldots ,\sigma _m\)  that are \(\mu \) -optimal with respect to \(\xi _1,\ldots ,\xi _m\) ,
at least one pair \(\sigma _i,\sigma _j\) 
satisfies \(\rho _N(\sigma _i,\sigma _j)\le \nu _1\)  or \(\rho _N(\sigma _i,\sigma _j)\ge \nu _2\) . Informally,
the m-OGP means that one cannot find \(m\) 
near optimal solutions for \(m\)  instances such that all \(m(m-1)/2\)  pairs of distances lie in the interval \((\nu _1,\nu _2)\) .
Clearly the case \(m=2\)  boils down to the e-OGP discussed earlier.
In many applications the difference
between \(\nu _1\)  and \(\nu _2\)  is often significantly smaller than the value of \(\nu _1\)  itself,
that is \(\nu _1\approx \nu _2\) . Thus, roughly speaking
the m-OGP means that one cannot find \(m\)  near optimal solutions so that all pairwise distances are \(\approx \nu _1\) .
The first usage of OGP as an obstruction to algorithms was adopted by Gamarnik and Sudan
in [1]}. The first application of
m-OGP as an obstruction to algorithms was adopted by Rahman and Virag in [2]}.
While their variant of m-OGP proved useful for some applications
as in Gamarnik and Sudan [3]},
and Coja-Oghlan, Haqshenas and Hetterich [4]},
since then the definition of m-OGP has been extended
to ”less symmetric” variants as one by Wein in [5]} and by Bresler and Huang
in [6]}. We will
not discuss the nature of these extensions and instead refer to the aforementioned references for further details.
e-OGP was introduced in Chen et al. [7]}.
<FIGURE>