Part of Advances in Neural Information Processing Systems 6 (NIPS 1993)
Scott Kirkpatrick, Géza Györgyi, Naftali Tishby, Lidror Troyansky
The satisfiability of random CNF formulae with precisely k vari(cid:173) ables per clause ("k-SAT") is a popular testbed for the performance of search algorithms. Formulae have M clauses from N variables, randomly negated, keeping the ratio a = M / N fixed . For k = 2, this model has been proven to have a sharp threshold at a = 1 between formulae which are almost aways satisfiable and formulae which are almost never satisfiable as N --jo 00 . Computer experi(cid:173) ments for k = 2, 3, 4, 5 and 6, (carried out in collaboration with B. Selman of ATT Bell Labs). show similar threshold behavior for each value of k. Finite-size scaling, a theory of the critical point phenomena used in statistical physics, is shown to characterize the size dependence near the threshold. Annealed and replica-based mean field theories give a good account of the results.
"Permanent address: IBM TJ Watson Research Center, Yorktown Heights, NY 10598 USA. (kirk@watson.ibm.com) Portions of this work were done while visiting the Salk Institute, with support from the McDonnell-Pew Foundation.