Constraint satisfaction problems and optimization problems which belong to NP-complete class are believed to be very difficult to solve in the worst case. However, most instances arising in practice might be very easy to solve, therefore need studies in the sense of average complexity. Statistical physics, especially cavity method from spin glass theory, is particularly suitable to give an "Heuristic" approach on average complexity  studies of these problems.

The first part of this talk will  give a review> on statistical physics studies on random satisfiability problem, on topics of satisfiability threshold and solution space organization. The second part of the talk will introduce our recent work on random quantified satisfiability problems, which can be seen as an attempt to use statistical physics on problems harder than NP-complete.