Weak lumpability in the k-SAT problem

Authors
Grinfeld, N Knight, PA
Citation
N. Grinfeld et Pa. Knight, Weak lumpability in the k-SAT problem, APPL MATH L, 13(6), 2000, pp. 49-53
Citations number
8
Categorie Soggetti
Mathematics
Journal title
APPLIED MATHEMATICS LETTERS
ISSN journal
08939659 → ACNP
Volume
13
Issue
6
Year of publication
2000
Pages
49 - 53
Database
ISI
SICI code
0893-9659(200008)13:6<49:WLITKP>2.0.ZU;2-F
Abstract
In this note, we discuss a Markov chain formulation of the k-SAT problem an d the propel-ties of the resulting transition matrix. The motivation behind this work is to relate the phase transition in the k-SAT problem to the ph enomenon of "cut-off" in Markov chains. We use the idea of weak-lumpability to reduce the dimension of our transition matrix to manageable proportions . (C) 2000 Elsevier Science Ltd. All rights reserved.