InterJournal Complex Systems, 81 Status: Accepted |
Manuscript Number: [81] Submission Date: 963011 |
Moments of satisfaction: statistical properties of a large random K-CNF formula |
Subject(s): CX.07
Category: Brief Article
Abstract:
Little is known about the distribution and structure of satisfying assignments of large K-CNF formulae. One interesting feature, observed by numerical simulations, is that for K >= 2, there is a sharp transition from a phase in which almost all formulae are satisfiable to a phase in which almost all formulae are un-satisfiable, as the ratio alpha= M/N goes through some critical value. So far there is no complete theoretical understanding of this phenomenon for K>2. In this paper we study the sat-assignment distribution and overlap, of a large random K-CNF formula. In particular, we study analytically the second, third and fourth moments of the number of satisfying assignments and overlap between satisfying assignments. We show that for K>4 the average overlap between satisfying assignments undergoes a discontinues (first order) transition from a low to high overlap of sat-assignments. This transition occurs at a value of alpha which is just below the numerically observed critical value. Similar, higher order, transition occur % for K=3,4 for higher moments of the distribution for larger K. The transition in the overlap is observed numerically even for N = 20.
Retrieve Manuscript |
Submit referee report/comment |