Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios

Details Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios

2006-09-18

arxiv.org/abs/cs/0609101v2

J. Phys. A: Math. Theor. 40, 867-886 (2007)

Computer Science

Computational Complexity

8 pages of text and 7 of appendices; updated to take into account comments received on the first version; to be published on J

Scientific paper

For large clause-to-variable ratio, typical K-SAT instances drawn from the uniform distribution have no solution. We argue, based on statistical mechanics calculations using the replica and cavity methods, that rare satisfiable instances from the uniform distribution are very similar to typical instances drawn from the so-called planted distribution, where instances are chosen uniformly between the ones that admit a given solution. It then follows, from a recent article by Feige, Mossel and Vilenchik, that these rare instances can be easily recognized (in O(log N) time and with probability close to 1) by a simple message-passing algorithm.

Affiliated with

Also associated with

No associations

Rating

Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios 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 Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647209