Weak lumpability in the k-SAT problem

Research output: Contribution to journalArticle

3 Citations (Scopus)

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

Keywords

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

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

Cite this