Weak lumpability in the k-SAT problem

DOI10.1016/S0893-9659(00)00053-7MaRDI QIDQ1585561zbMATH OpenFDO

Authors M. Grinfeld, Philip A. Knight

Publication date 16 November 2000

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

Full work available at URL https://doi.org/10.1016/S0893-9659(00)00053-7

zbMATH Keywords

\(k\)-SATMarkov chainsphase transitionweak lumpability

Mathematics Subject Classification ID

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

Recommendations

• On the phase transitions of (k, q)-SAT
• On weak lumpability of a finite Markov chain
• On threshold properties of k-SAT: An additive viewpoint
• The SAT phase transition
• The asymptotic k-SAT threshold

Cites work

• A threshold for unsatisfiability
• scientific article; zbMATH DE number 3145626 (Why is no real title available?)
• scientific article; zbMATH DE number 4082591 (Why is no real title available?)
• Probability approximations via the Poisson clumping heuristic
• Sharp thresholds of graph properties, and the k-sat problem
• The cutoff phenomenon in finite Markov chains.

Cited in

(4)

• Markov property for a function of a Markov chain: A linear algebra approach
• Systems of random equations over finite algebraic structures
• NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT ≥ k ,r-UNLSAT ≥ k )
• On the Relationships Between Lumpability and Filtering of Finite Stochastic Systems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1585561)