Phase coexistence and finite-size scaling in random combinatorial problems

Abstract

We study an exactly solvable version of the famous random Boolean\nsatisfiability problem, the so called random XOR-SAT problem. Rare events are\nshown to affect the combinatorial ``phase diagram'' leading to a coexistence of\nsolvable and unsolvable instances of the combinatorial problem in a certain\nregion of the parameters characterizing the model. Such instances differ by a\nnon-extensive quantity in the ground state energy of the associated diluted\nspin-glass model. We also show that the critical exponent $\\nu$, controlling\nthe size of the critical window where the probability of having solutions\nvanishes, depends on the model parameters, shedding light on the link between\nrandom hyper-graph topology and universality classes. In the case of random\nsatisfiability, a similar behavior was conjectured to be connected to the onset\nof computational intractability.\n