Question

In no more than half a page, explain and discuss the phase transition phenomenon in random Random 3-SAT. Note: This requires some research. Marks will depend on the quality of presentation, and the depth and breadth of the explanation?

Answer 1

An interesting property of uniform Random-3-SAT is the occurrence of a phase transition phenomenon [CKT91], i.e., a rapid change in solubility which can be observed when systematically increasing (or decreasing) the number of k clauses for fixed problem size n. More precisely, for small k almost all formulae can be satisfied. At some critical value k=k', the probability of generating an instance that can be satisfied drops sharply to almost zero. Beyond k', almost all instances are not satisfied. Intuitively, k' characterizes the transition between a region of under-constrained instances which are almost certainly soluble, to over-constrained instanced which are mostly insoluble. For Random-3-SAT, if n is large this phase transition occurs approximately at k' = 4.26 and for smaller n, the critical clauses/variable ratio k'/n is slightly higher. Furthermore, for growing n the transition becomes increasingly sharp. The phase transition would not be very interesting in the context of evaluating SLS algorithms, didn't empirical analyses show that problems from the phase transition region of uniform Random-3-SAT tend to be particularly hard for both systematic SAT solvers and SLS algorithms. Striving for testing their algorithms on hard problem instances, many researchers used test-sets sampled from the phase transition region of uniform Random-3-SAT. Although, similar phase transition phenomena have been observed for other sub classes of SAT, including uniform Random-k-SAT with k >= 4, but these have never gained the popularity of uniform Random-3-SAT. Maybe, one of the reasons for this is the prominent role of 3-SAT as a prototypical and syntactically particularly simple NP-complete problem.