The K-SAT Problem is a problem of optimization of Boolean variables. It is very important because it was the first to be shown NP-Complete. Many algorithms were built to search a solution of the problem, but only the Survey Propagation, until today, is the best algorithm, which finds solutions of K-SAT Problems in the "hard-sat region".
We have analyzed the Survey Propagation Algorithm to find solutions of 3-SAT Problems very close to the Transition Phase. We have found a new limit of performance of the Survey Propagation Algorithm and a new no-trivial relation between the Complexity and the number of free variables.