Some exact calculations for K-SAT on trees

Details Some exact calculations for K-SAT on trees Some exact calculations for K-SAT on trees

2011-10-10

arxiv.org/abs/1110.2065v1

Physics

Condensed Matter

Statistical Mechanics

22 pages, 5 figures

Scientific paper

We consider the K-satisfiability problem on a regular d-ary rooted tree. For this model, we demonstrate how we can calculate in closed form, the moments of the total number of solutions as a function of d and K, where the average is over all realizations, for a fixed assignment of the surface variables. We find that different moments pick out different 'critical' values of d, below which they diverge as the total number of variables on the tree goes to infinity and above which they decay. We show that K-SAT on the random graph also behaves similarly. We also calculate exactly the fraction of instances that have solutions for all K. On the tree, this quantity decays to 0 (as the number of variables increases) for any d>1. However the recursion relations for this quantity have a non-trivial fixed-point solution which indicates the existence of a different transition in the interior of an infinite rooted tree.

Affiliated with

Also associated with

No associations

Rating

Some exact calculations for K-SAT on trees 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 Some exact calculations for K-SAT on trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some exact calculations for K-SAT on trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-147399