# When Formulas Freeze: Phase Transitions in Computation

# When Formulas Freeze: Phase Transitions in Computation

Certain formulas, such as the 3-SAT formula, undergo a phase transition from almost certain satisfiability to almost certain unsatisfiability when the number of constraints per variable reaches a critical threshold. This transition is comparable to the freezing of water and also occurs in many other NP-complete problems such as graph coloring and integer partitioning. This chapter first considers some experimental results on random 3-SAT and assumes that a phase transition exists. It then explores some simple phase transitions in random graphs and shows how to compute the size of *k*-cores, along with the degrees at which they first appear. It also looks at random *k*-SAT formulas and demonstrates how to prove upper and lower bounds on the critical density of clauses. Furthermore, it describes simple search algorithms as flows through state space before concluding with a discussion of recent advances inspired by techniques in statistical physics.

*Keywords:*
formulas, 3-SAT, phase transitions, random graphs, k-cores, clauses, search algorithms, state space, statistical physics, lower bounds

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .