On the behaviour of random <i>K</i>-SAT on trees

作     者：Krishnamurthy, Supriya Sumedha 

作者机构：Stockholm Univ Dept Phys SE-10691 Stockholm Sweden KTH Sch Comp Sci & Commun SE-10044 Stockholm Sweden Natl Inst Sci Educ & Res Inst Phys Campus Bhubaneswar 751005 Orissa India 

出 版 物：《JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT》 (统计力学杂志：理论和实验)

年 卷 期：2012年第2012卷第05期

页      面：P05009-P05009页

核心收录：

学科分类：07[理学] 070201[理学-理论物理] 0702[理学-物理学] 0801[工学-力学（可授工学、理学学位）] 

基　　金：Swedish Research Council 

主　　题：solvable lattice models exact results random graphs networks typical-case computational complexity 

摘      要：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 - 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.