In this note, we discuss a Markov chain formulation of the k-SAT problem and the properties of the resulting transition matrix. The motivation behind this work is to relate the phase transition in the k-SAT problem to the phenomenon of "cut-off" in Markov chains. We use the idea of weak-lumpability to reduce the dimension of our transition matrix to manageable proportions.
- Markov chains
- phase transition