  In this paper we introduce a new algorithm to study some NP-complete
problems. This algorithm is a Markov Chain Monte Carlo (MCMC) inspired by the
cavity method developed in the study of spin glass. We will focus on the
maximum clique problem and we will compare this new algorithm with several
standard algorithms on some DIMACS benchmark graphs and on random graphs. The
performances of the new algorithm are quite surprising. Our effort in this
paper is to be clear as well to those readers who are not in the field.
