Article ID Journal Published Year Pages File Type
4649733 Discrete Mathematics 2009 15 Pages PDF
Abstract

We study threshold phenomena for a large class of random constraint satisfaction problems over finite domains. Our main contribution is a complete classification of the nature (sharp or coarse) of the SAT–UNSAT transition for random Boolean CSPs, which is based on easily decidable properties.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
The SAT–UNSAT transition for random constraint satisfaction problems
Authors
, ,