Weak lumpability in the k-SAT problem

M. Grinfeld; P.A. Knight

doi:10.1016/S0893-9659(00)00053-7

Weak lumpability in the k-SAT problem

M. Grinfeld, P.A. Knight

Mathematics And Statistics

Research output: Contribution to journal › Article › peer-review

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 language	English
Pages (from-to)	49-53
Number of pages	5
Journal	Applied Mathematics Letters
Volume	13
Issue number	6
DOIs	https://doi.org/10.1016/S0893-9659(00)00053-7
Publication status	Published - 30 Aug 2000

Keywords

k-SAT
Markov chains
phase transition
weak-lumpability

Access to Document

10.1016/S0893-9659(00)00053-7

Cite this

@article{6a9e9b8333644713b72326f9796182eb,

title = "Weak lumpability in the k-SAT problem",

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.",

keywords = "k-SAT, Markov chains, phase transition, weak-lumpability",

author = "M. Grinfeld and P.A. Knight",

year = "2000",

month = aug,

day = "30",

doi = "10.1016/S0893-9659(00)00053-7",

language = "English",

volume = "13",

pages = "49--53",

journal = "Applied Mathematics Letters",

issn = "0893-9659",

number = "6",

}

TY - JOUR

T1 - Weak lumpability in the k-SAT problem

AU - Grinfeld, M.

AU - Knight, P.A.

PY - 2000/8/30

Y1 - 2000/8/30

N2 - 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.

AB - 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.

KW - k-SAT

KW - Markov chains

KW - phase transition

KW - weak-lumpability

UR - http://www.scopus.com/inward/record.url?scp=0039838912&partnerID=8YFLogxK

U2 - 10.1016/S0893-9659(00)00053-7

DO - 10.1016/S0893-9659(00)00053-7

M3 - Article

AN - SCOPUS:0039838912

VL - 13

SP - 49

EP - 53

JO - Applied Mathematics Letters

JF - Applied Mathematics Letters

SN - 0893-9659

IS - 6

ER -

Weak lumpability in the k-SAT problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this