Phase coexistence and finite-size scaling in random combinatorial problems

Publisher Website
Google Scholar
Abstract
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.