InterJournal Complex Systems, 64
Status: Accepted
Manuscript Number: [64]
Submission Date: 963011
Phase transition and search cost in the shcSAT problem
Author(s): R Monasson ,Riccardo Zecchina , S Kirkpatrick

Subject(s): CX.07

Category: Brief Article

Abstract:

We give analytical and numerical results concerning a new Satisfiability 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 first order RSB transitions---and the onset of exponential behaviour in search algorithms are identified.

Retrieve Manuscript
Submit referee report/comment


Public Comments: