The SAT Phase Transition

Simple item page
dc.creatorXu, Ke
dc.creatorLi, Wei
dc.date2000-05-22
dc.date2000-05-23
dc.date.accessioned2026-07-07T03:16:14Z
dc.date.available2026-07-07T03:16:14Z
dc.descriptionPhase 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.
dc.description13 pages, 3 figures
dc.identifierhttps://arxiv.org/abs/cs/0005024
dc.identifierhttp://arxiv.org/abs/cs/0005024
dc.identifierThe SAT Phase Transition. Science in China, Series E, 42(5):494-501, 1999
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30273
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.subjectF.2.m; I.2.8
dc.titleThe SAT Phase Transition
dc.typetext

Files

Collections

arXiv