The SAT Phase Transition
<|reference_start|>The SAT Phase Transition: 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.<|reference_end|>
@article{xu2000the,
    title={The SAT Phase Transition},
    author={Ke Xu and Wei Li},
    journal={The SAT Phase Transition. Science in China, Series E,
  42(5):494-501, 1999},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0005024},
    primaryClass={cs.AI cs.CC}
}