Abstract
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 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.
Users
Please
log in to take part in the discussion (add own reviews or comments).