Complexity of max-sat using stochastic algorithms

Hill-climbing has been shown to be more effective than ex-haustive search in solving satisfiability problems.Also, it has been used either by itself or in combination with other meth-ods to solve the most difficult region of SAT, the phase tran-sition. We show that hill-climbing also finds SAT problems difficult around the phase transition. It too follows an easy-hard-eays transition