InterJournal Complex Systems, 81
Status: Accepted
Manuscript Number: [81]
Submission Date: 963011
Moments of satisfaction: statistical properties of a large random K-CNF formula
Author(s): Lidror Troyansky , Naftali Tishby

Subject(s): CX.07

Category: Brief Article


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

Public Comments: