Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 49-53 |
Number of pages | 5 |
Journal | Applied Mathematics Letters |
Volume | 13 |
Issue number | 6 |
DOIs | |
Publication status | Published - 30 Aug 2000 |
Keywords
- k-SAT
- Markov chains
- phase transition
- weak-lumpability