procedures at the critical value of m=n in Random 3-SAT. More recent studies, (e.g. Parkes region, the average cost increases with m=n due to the decreasing number of solutions per m=n although the number of solutions per instance continues to fall. Several researchers of the backbone of satisable Random 3-SAT instances. For satisable SAT instances, the Variables which appear in these entailed literals are each forced to take particular truth ure WSat is strongly in uenced by the size of the backbone. This suggests that the peak in average WSat cost near the critical value as the control parameter is increased may be due of the WSat algorithm and the Random k-SAT distribution and discuss the experimental we identify remarkable pattern in WSat's search behaviour which clearly distinguishes high cost from lower cost instances of certain backbone size. WSat is usually drawn
