Some results for k-SAT on trees

8th STATPHYS-KOLKATA

Sumedha^1 ; Krishnamurthy, Supriya^2

National Institute of Science Education and Research, Institute of Physics Campus, Odisha, Bhubaneswar

751 005, India^1

Department of Physics, Stockholm University, Stockholm

SE-106 91, Sweden^2

关键词: Cavity method;    Infinite trees;    NP Complete;    Random graphs;    Random k-Sat;    Random K-SAT problem;    Time algorithms;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/638/1/012017/pdf
DOI  :  10.1088/1742-6596/638/1/012017

来源: IOP

【 摘 要 】

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.