1996/03/02 by Rémi Monasson, Remi Monasson, Riccardo Zecchina · 4 citations
Computer Science · Mathematics · Physics and Astronomy · #Discrete mathematics #Entropy (arrow of time) #Mathematics #Physical system #Physics #Quantum mechanics #Rough Sets and Fuzzy Logic #Satisfiability #Statistical Mechanics and Entropy #Statistical mechanics #Statistical physics #Theoretical and Computational Physics #cond-mat
paper · pdf · doi:10.1103/physrevlett.76.3881
revtex, 11 pages + 1 figure
arxiv created 1996/03/02 · openalex publication_date 1996/05/20 · arxiv updated 2009/11/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
The threshold behavior of the K-satisfiability problem is studied in the framework of the statistical mechanics of random diluted systems. We find that at the transition the entropy is finite and hence that the transition itself is due to the abrupt appearance of logical contradictions in all solutions and not to the progressive decreasing of the number of these solutions down to zero. A physical interpretation is given for the different cases K\phantom\rule0ex0ex=\phantom\rule0ex0ex1, K\phantom\rule0ex0ex=\phantom\rule0ex0ex2, and K\ensuremath≥3.