  The MaxClique problem, finding the largest complete subgraph in an
Erd{\"o}s-R{\'e}nyi $G(N,p)$ random graph in the large $N$ limit, is a
well-known example of a simple problem for which finding any approximate
solution within a factor of $2$ of the known, probabilistically determined
limit, appears to require P$=$NP. This type of search has practical importance
in very large graphs. Algorithmic approaches run into phase boundaries long
before they reach the size of the largest likely solutions. And, most
intriguing, there is an extensive literature of \textit{challenges} posed for
concrete methods of finding maximum naturally occurring as well as artificially
hidden cliques, with computational costs that are at most polynomial in the
size of the problem.
  We use the probabilistic approach in a novel way to provide a more insightful
test of constructive algorithms for this problem. We show that extensions of
existing methods of greedy local search will be able to meet the
\textit{challenges} for practical problems of size $N$ as large as $10^{10}$
and perhaps more. Experiments with spectral methods that treat a single large
clique of size $\alpha N^{1/2}$ \textit{planted} in the graph as an impurity
level in a tight binding energy band show that such a clique can be detected
when $\alpha \geq \approx1.0$. Belief propagation using a recent
\textit{approximate message passing} (\textbf{AMP}) scheme of inference pushes
this limit down to $\alpha \sim \sqrt{1/e}$. Exhaustive local search (with
early stopping when the planted clique is found) does even better on problems
of practical size, and proves to be the fastest solution method for this
problem.
