Weak lumpability in the \(k\)-SAT problem

DOI10.1016/S0893-9659(00)00053-7zbMath0958.60069MaRDI QIDQ1585561

Michael Grinfeld, Philip A. Knight

Publication date: 16 November 2000

Published in: Applied Mathematics Letters (Search for Journal in Brave)

zbMATH Keywords

Markov chainsphase transitionweak lumpability\(k\)-SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Related Items (3)

On the Relationships Between Lumpability and Filtering of Finite Stochastic Systems ⋮ Markov property for a function of a Markov chain: A linear algebra approach ⋮ Systems of random equations over finite algebraic structures

Cites Work

• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• Probability approximations via the Poisson clumping heuristic
• Sharp thresholds of graph properties, and the $k$-sat problem
• The cutoff phenomenon in finite Markov chains.

This page was built for publication: Weak lumpability in the \(k\)-SAT problem