Portal de Periódicos da CAPES

Combinatorial sharpness criterion and phase transition classification for random CSPs

2004; Elsevier BV; Volume: 190; Issue: 2 Linguagem: Inglês

10.1016/j.ic.2004.01.002

1090-2651

Nadia Creignou, Hervé Daudé,

Complexity and Algorithms in Graphs

We investigate the nature of the phase transition (sharp or coarse) for random constraint satisfaction problems. We first give a sharp threshold criterion specified for CSPs, which is derived from Friedgut–Bourgain’s one. Thus, we get a complete and precise classification of the nature of the threshold for symmetric Boolean CSPs. In particular we show that it is governed by two local properties strongly related to the problems 1−SAT and 2−XOR−SAT .