Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2001-03-08
J. Phys. A 34 (2001) 4615
Physics
Condensed Matter
Disordered Systems and Neural Networks
10 pages, 5 figures, to appear in J. Phys. A. v2: link to the XOR-SAT probelm added
Scientific paper
10.1088/0305-4470/34/22/303
We study an exactly solvable version of the famous random Boolean satisfiability 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 $\nu$, 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 satisfiability, a similar behavior was conjectured to be connected to the onset of computational intractability.
Leone Maurizio
Ricci-Tersenghi Federico
Zecchina Riccardo
No associations
LandOfFree
Phase coexistence and finite-size scaling in random combinatorial problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Phase coexistence and finite-size scaling in random combinatorial problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Phase coexistence and finite-size scaling in random combinatorial problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-541084