On the behaviour of random K-SAT and Balanced SAT on trees

by Prof. Supriya Krishnamurthy (SU Physics)

Tuesday 18 Dec 2012, 13:30 → 14:30 Europe/Stockholm

122:026

Satisfiability has been a fundamental problem for almost 40 years in computer science. It has also attracted a lot of attention in physics, because of its close connection with the theory of mean-field spin glasses, as a result of which many techniques used in the latter are directly applicable in K-SAT. Applying these techniques to K-SAT has shown that there are a number of phase transitions occuring in the problem, besides the main solvability transition - the most interesting of these being the clustering transition. One point about these calculations is that they are usually done on tree graphs, but are used to predict phenomena in random graphs. Recently, we have looked at a quantity on the tree, which is the equivalent of the solvability transition on the random graph. The recursions we set up are very easy to generalize to a variety of SAT problems, and give exact results for 2 SAT and surprisingly close results for the computationally interesting case of 3 SAT. For higher K, curiously enough, the numbers are exactly the same as those predicted for the threshold after which clustering occurs in solution space.