Exact phase transition of backtrack-free search with implications on the power of greedy algorithms

摘要：

Backtracking is a basic strategy to solve constraint satisfaction problems (CSPs). A satisfiable CSP instance is backtrack-free if a solution can be found without encountering any dead-mid during a backtracking search, implying that the instance is easy to solve. We prove an exact phase transition of backtrack-free search in some random CSPs, namely in Model RB and in Model HD. This is the first time an exact phase transition of backtrack-free search can be identified on some random CSPs. Our technical results also have interest ing implications on the power of greedy algorithms, on the width of superlinear dense random hypcrgraphs and on the exact satisfiability threshold of random CSPs.

作者: Liang Li Tian Liu Ke Xu

作者单位: Key Laboratory of High Confidence Software Technologies (Peking University), Ministry of Education. National Lab of Software Development Environment, School of Computers. Beihang University. Beijing 1

会议类型: 国际会议

会议名称: International Workshop on Statistical Physics and Computer Sciences(统计物理与计算机科学交叉研究国际研讨会 )

会议地点: 北京

会议语种:英文

页码: 226-240

在线出版日期: 2010-07-08（万方平台首次上网日期，不代表论文的发表时间）