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度变量的分包操作,避免了陈刘和刘的算法中的瓶颈。为了简化案例分析,我们还引入了一个一般的分析框架,可以用于其他问题。

0
下载
关闭预览

相关内容

专知会员服务
75+阅读 · 2021年3月16日
专知会员服务
51+阅读 · 2020年9月7日
【经典书】Python金融大数据分析,566页pdf
专知会员服务
117+阅读 · 2020年8月1日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
Python图像处理,366页pdf,Image Operators Image Processing in Python
商业数据分析,39页ppt
专知会员服务
157+阅读 · 2020年6月2日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
已删除
inpluslab
8+阅读 · 2019年10月29日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
Arxiv
0+阅读 · 2021年7月5日
Arxiv
0+阅读 · 2021年7月3日
Arxiv
0+阅读 · 2021年6月30日
VIP会员
相关VIP内容
专知会员服务
75+阅读 · 2021年3月16日
专知会员服务
51+阅读 · 2020年9月7日
【经典书】Python金融大数据分析,566页pdf
专知会员服务
117+阅读 · 2020年8月1日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
Python图像处理,366页pdf,Image Operators Image Processing in Python
商业数据分析,39页ppt
专知会员服务
157+阅读 · 2020年6月2日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
相关资讯
已删除
inpluslab
8+阅读 · 2019年10月29日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
Top
微信扫码咨询专知VIP会员