Phase coexistence and finite-size scaling in random combinatorial problems

Abstract

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 $ν$, 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.

10 pages, 5 figures, to appear in J. Phys. A. v2: link to the XOR-SAT probelm added