2001/03/15 by M. Leone, Michele Leone, Federico Ricci‐Tersenghi +3 · 1 citation
Computer Science · Physics and Astronomy · #Constraint Satisfaction and Optimization #Data Management and Algorithms #Rough Sets and Fuzzy Logic #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.1088/0305-4470/34/22/303
published as J. Phys. A 34 (2001) 4615 · 10 pages, 5 figures, to appear in J. Phys. A. v2: link to the XOR-SAT probelm added
arxiv created 2001/03/15 · openalex publication_date 2001/05/24 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
We study an exactly solvable version of the well known random Boolean satisfiability (SAT) problem, the so-called random XOR-SAT problem. Rare events are shown to affect the combinatorial `phase diagram' leading to a coexistence of solvable and unsolvable instances of the combinatorial problem in a certain region of the parameters characterizing the model. Such instances differ by a non-extensive quantity in the ground state energy of the associated diluted spin glass model. We also show that the critical exponent ν, controlling the size of the critical window where the probability of having solutions vanishes, depends on the model parameters, shedding light on the link between random hyper-graph topology and universality classes. In the case of random SAT, a similar behaviour was conjectured to be connected to the onset of computational intractability.