Imagine a club with \(N\)  members in which about 50% of the \(N(N-1)/2\)  member pairs know each other personally, and the remaining
50% of the members do not. You want to find a largest clique
in this club, namely the largest group of members out of the \(N\)  members
who all know each other. What is the typical size \(c^*\)  of such a clique? How easy is it to find one?
This question can be modeled as the problem of finding a largest fully connected sub-graph (formally called a ”clique”) in a random
Erdös-Rényi graph \(\mathbb {G}(N,1/2)\) , which is a graph on \(N\)  nodes where every pair of nodes is connected with probability \(1/2\) , independently for all pairs.
The first question regarding the largest clique size \(c^*\)  is a textbook example of the so-called probabilistic method,
a simple application of which tells us that \(c^*\)  is likely to be near \(2\log _2 N\)  with high degree of certainty as \(N\) 
gets large [1]}.
A totally different matter is the problem of actually finding such a clique and this is where the embarrassment begins. Richard Karp, one of the founding fathers
of the algorithmic complexity theory, observed in his 1976 paper [2]}
that a very simple algorithm, both in terms of the analysis and the implementation,
finds a clique of roughly half-optimum size, namely with about \(\log _2 N\)  members, and challenged to do better. The problem
is still open and this is embarrassing for two reasons: (a) The best known algorithm, namely the one above,
is also an extremely naive one. So it appears that the significant progress that the algorithmic community has
achieved
over the past decades in constructing ever more clever and powerful algorithms, is totally helpless in improving upon this extremely simple and naive
algorithm; (b) We don't have a workable
theory of algorithmic hardness which rigorously explains why finding cliques of size half-optimum is easy,
and improving on it does not seem possible within the
realm of polynomial time algorithms. The classical \(P\ne NP\)  paradigm and its variants is of no help here, more on this below.
An approach based on the solution space landscape
can be used to rule out Markov Chain Monte Carlo (MCMC) algorithms for finding cliques larger than half-optimum
by showing that the associated chain mixes at scale
larger than polynomial time, and thus ruling out the MCMC algorithm [3]}.
The method however does not appear extendable
to other types algorithms which are not based on MCMC method.
