Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios
Fabrizio AltarelliRémi MonassonFrancesco ZamponiPublished in: CoRR (2006)
Keyphrases
- message passing
- boolean formula
- belief propagation
- propositional satisfiability
- inference in graphical models
- sum product algorithm
- matrix multiplication
- satisfiability problem
- computational complexity
- satisfiability testing
- sat solvers
- truth assignment
- search algorithm
- image processing
- shared memory
- loopy belief propagation
- probabilistic inference
- graph cuts
- sat problem
- distributed systems
- markov random field
- search space
- generalized belief propagation
- preprocessing