The SAT Phase Transition

2000/05/23 by Ke Xu, Wei Li · 3 citations
Computer Science · #cs.AI #cs.CC

paper · pdf

published as The SAT Phase Transition. Science in China, Series E, 42(5):494-501, 1999 · 13 pages, 3 figures

arxiv created 2000/05/23 · arxiv updated 2009/11/30

Abstract

Phase transition is an important feature of SAT problem. For random k-SAT model, it is proved that as r (ratio of clauses to variables) increases, the structure of solutions will undergo a sudden change like satisfiability phase transition when r reaches a threshold point. This phenomenon shows that the satisfying truth assignments suddenly shift from being relatively different from each other to being very similar to each other.

Cited by

• Outsourcing SAT-based Verification Computations in Network Security
• Degrees of Freedom for Critical Random 2-SAT
• Phase Transitions in Decision Problems Over Odd-Sized Alphabets

Related

• Phase Transition in Unrestricted Random SAT
• Degrees of Freedom for Critical Random 2-SAT
• 2+p-SAT: Relation of Typical-Case Complexity to the Nature of the Phase Transition
• Easy/Hard Transition in k-SAT
• The Asymptotic Order of the k-SAT Threshold