Weak lumpability in the k-SAT problem

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


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 languageEnglish
Pages (from-to)49-53
Number of pages5
JournalApplied Mathematics Letters
Issue number6
Publication statusPublished - 30 Aug 2000


  • k-SAT
  • Markov chains
  • phase transition
  • weak-lumpability


Dive into the research topics of 'Weak lumpability in the k-SAT problem'. Together they form a unique fingerprint.

Cite this