  Finding a Maximum Clique is a classic property test from graph theory; find
any one of the largest complete subgraphs in an Erd\"os-R\'enyi G(N, p) random
graph. We use Maximum Clique to explore the structure of the problem as a
function of N, the graph size, and K, the clique size sought. It displays a
complex phase boundary, a staircase of steps at each of which 2log2 N and Kmax,
the maximum size of a clique that can be found, increases by 1. Each of its
boundaries has a finite width, and these widths allow local algorithms to find
cliques beyond the limits defined by the study of infinite systems. We explore
the performance of a number of extensions of traditional fast local algorithms,
and find that much of the "hard" space remains accessible at finite N. The
"hidden clique" problem embeds a clique somewhat larger than those which occur
naturally in a G(N, p) random graph. Since such a clique is unique, we find
that local searches which stop early, once evidence for the hidden clique is
found, may outperform the best message passing or spectral algorithms.
