Phase transition and search cost in the 2+p-sat problem
Rémi Monasson, Riccardo Zecchina, Sivyllis Kirkpatrick, B. Selman, Lidror Troyansky · 1996
this paper, we give a preliminary discussion of a new SAT model, hereafter referred to as 2+p--SAT model. The model interpolates smoothly between 2--SAT and 3--SAT, and allows us to address the above issue. Since this model is relatively amenable to computer simulation, we have begun to explore the validity of the predictions of the theory in the range K = 2 to 3 generated by the 2+p model. We are also able to see if there are observable side effects of the change from a continuous to a first-order RSB transition. The results reported here are preliminary, and will be extended, but they already show impressive agreement with the theory, and suggest some exciting consequences of the continuous to first-order transition. 2 The 2+p--SAT model