In this paper, we prove that the general CNF satisfiability problem can be solved in $O^*(1.0646^L)$ time, where $L$ is the length of the input CNF-formula (i.e., the total number of literals in the formula), which improves the current bound $O^*(1.0652^L)$ given by Chen and Liu 12 years ago. Our algorithm is a standard branch-and-search algorithm analyzed by using the measure-and-conquer method. We avoid the bottleneck in Chen and Liu's algorithm by simplifying the branching operation for 4-degree variables and carefully analyzing the branching operation for 5-degree variables. To simplify case-analyses, we also introduce a general framework for analysis, which may be able to be used in other problems.
翻译:在本文中,我们证明CNF的可测量性问题可以用美元(1.0646 ⁇ L)的时间来解决,因为美元是输入的CNF-公式(即公式中的字数总数)的长度(即公式中的字数),这改善了陈和刘12年前提供的目前约束值(1.0652 ⁇ L)美元。我们的算法是一种标准的分支和搜索算法,通过使用计量和算法进行分析。我们通过简化四度变量的分包操作并仔细分析5度变量的分包操作,避免了陈刘和刘的算法中的瓶颈。为了简化案例分析,我们还引入了一个一般的分析框架,可以用于其他问题。