Paper available on the Random K-Satisfiability Problem

[Riccardo Zecchina - tel.11-5647358, fax. 11-5647399]

 The following paper on algorithmic complexity is available by FTP.  


  STATISTICAL MECHANICS OF THE RANDOM K-SATISFIABILITY PROBLEM

  by Remi Monasson and Riccardo Zecchina.


  ABSTRACT:  The Random K-Satisfiability Problem, consisting in verifying the
 existence of an assignment of $N$ Boolean variables that satisfy a set of
 $M=\alpha N$ random logical clauses containing $K$ variables each, is studied
 using the replica symmetric framework of disordered systems. The detailed
 structure of the analytical solution is discussed for the different cases of
 interest $K=2$, $K\ge 3$ and $K\gg 1$. We present an iterative scheme allowing
 to obtain exact and systematically improved solutions for the replica
 symmetric functional order parameter. The caculation of the number of
 solutions, which allowed us [Phys. Rev. Lett. 76, 3881 (1996)] to predict a
 first order jump at the threshold where the Boolean expressions become
 unsatisfiable with probability one, is thoroughly displayed. In the case
 $K=2$, the (rigourously known) critical value ($=1$) of the number of clauses
 per Boolean variable is recovered while for $K\ge 3$ we show that the system
 exhibits a replica symmetry breaking transition. The annealed approximation is
 proven to be exact for large $K$.

 (30 pages + 8 figures)
	
 Retrieval information:
 FTP-host:      ftp.polito.it
 FTP-pathname:  /pub/people/zecchina/tarksat.gz
 URL: ftp://ftp.polito.it/pub/people/zecchina