Coarse and Sharp Transitions for Random Generalized Satisfyability Problems
Nadia Creignou, Hervé Daudé · Birkhäuser Basel eBooks · 2004
We study threshold phenomena for random generalized satisfiability problems. These fundamental problems were defined by Schaefer, who gave a complete complexity classification. We give here a complete classification of the nature (coarse or sharp) of the threshold for all generalized satisfiability problems. This new classification is based on easily decidable local properties, and thus provides an exact probabilistic counterpart of Schaefer’s complexity result. ~T. Schaefer. The complexity of satisfiability problems, in Proceedings 10th STOC, San Diego (CA, USA), pages 216-226. Association for Computing Machinery, 1978.] These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.