Some results for k-SAT on trees
M. Leone Sumedha, Supriya Krishnamurthy · Journal of Physics Conference Series · 2015
Phase transitions in random k -SAT problems are connected to their computational complexity. While polynomical time algorithms are known to solve the problem for k = 2, for k ≥ 3 the problem is known to be NP-complete. Recently we have studied random k -SAT and many of its variants on regular infinite trees. We find that the solvability threshold for k = 2 matches the exact value of the threshold on regular random graphs. For higher k , the values are very close to those predicted using other techniques like cavity method.