On the behaviour of random K-SAT on trees
Journal of Statistical Mechanics: Theory and Experiment, 2012 (05):
P05009+ (11.05.2012)DOI: 10.1088/1742-5468/2012/05/p05009
Zusammenfassung
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.