Phase transition and search cost in the 2+p-sat problem
We give analytical and numerical results concerning a new Satissability problem for random Boolean expressions. Our model smoothly interpolates between the polynomial 2{SAT problem and the NP{complete 3{SAT problem. Possible consequences on the relationship between the statistical mechanics characterization of phase transitions { particularly smooth second order RSB and rst order RSB transitions { and the onset of exponential behaviour in search algorithms are identiied.