preprints available on Neuroprose

[Scott Kirkpatrick]

           **DO NOT FORWARD TO OTHER GROUPS**

FTP-host: archive.cis.ohio-state.edu

FTP-file: pub/neuroprose/kirkpatrick.critical.ps.Z
FTP-file: pub/neuroprose/kirkpatrick.nips93-statistical.ps.Z

Only soft copy is available.

The two above preprints are available for anonymous ftp in the 
Neuroprose archive.  Full titles and authors are:

Critical Behavior at the k-Satisfaction Threshold  (preprint),
by Scott Kirkpatrick and Bart Selman 

The Statistical Mechanics of k-Satisfaction,  (NIPS-6 preprint)
by S. Kirkpatrick, G. Gyorgyi, N. Tishby and L. Troyansky

abstracts follow: 
	
{Critical Behavior at the $k$-Satisfiability Threshold}


The satisfiability of random Boolean formulae with precisely $k$ variables 
per clause is a popular testbed for the performance of search algorithms in 
artificial intelligence and computer science. For $k = 2$, formulae are 
almost aways satisfiable when the ratio of clauses to variables is less than 1; 
for ratios larger than 1, the formulae are almost never satisfiable.
We present data showing a similar threshold behavior for higher values of $k$. 
We also show how finite-size scaling, a method from statistical physics, can 
be used to characterize size dependent effects near the threshold.
Finally, we commment on the relationship between thresholds and 
computational complexity.



{The Statistical Mechanics of $k$-Satisfaction}


The satisfiability of random CNF formulae with precisely $k$ variables 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 $\alpha = M/N$ fixed.
For $k = 2$, this model has been proven to have a sharp threshold
at $\alpha = 1$ between formulae which are almost aways satisfiable
and formulae which are almost never satisfiable as $N \rightarrow \infty$.
Computer experiments 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.