The decimation process in random k-SAT

Details The decimation process in random k-SAT The decimation process in random k-SAT

2011-02-15

arxiv.org/abs/1102.3145v1

Mathematics

Combinatorics

Scientific paper

Let F be a uniformly distributed random k-SAT formula with n variables and m clauses. Non-rigorous statistical mechanics ideas have inspired a message passing algorithm called Belief Propagation Guided Decimation for finding satisfying assignments of F. This algorithm can be viewed as an attempt at implementing a certain thought experiment that we call the Decimation Process. In this paper we identify a variety of phase transitions in the decimation process and link these phase transitions to the performance of the algorithm.

Affiliated with

Also associated with

No associations

Rating

The decimation process in random k-SAT does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The decimation process in random k-SAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The decimation process in random k-SAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-378836