On the behaviour of random K-SAT on trees
2012 (English)In: Journal of Statistical Mechanics: Theory and Experiment, ISSN 1742-5468, Vol. 2012, no 5, P05009- p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
2012. Vol. 2012, no 5, P05009- p.
exact results, networks, random graphs, solvable lattice models, typical-case computational complexity
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-98527DOI: 10.1088/1742-5468/2012/05/P05009ISI: 000305266900011ScopusID: 2-s2.0-84861804100OAI: oai:DiVA.org:kth-98527DiVA: diva2:537912
FunderSwedish Research CouncilICT - The Next Generation
QC 201206282012-06-282012-06-272013-04-11Bibliographically approved