资源分类
》 资源 》论文》Lower Bounds for Width-Restricted Clause Learning on Formulas of Small Width

Lower Bounds for Width-Restricted Clause Learning on Formulas of Small Width

2019-11-12 | |  81 |   48 |   0
Abstract Clause learning is a technique used by backtracking-based propositional satis?ability solvers, where some clauses obtained by analysis of con?icts are added to the formula during backtracking. It has been observed empirically that clause learning does not signi?cantly improve the performance of a solver when restricted to learning clauses of small width only. This experience is supported by lower bound theorems. It is shown that lower bounds on the runtime of width-restricted clause learning follow from lower bounds on the width of resolution proofs. This yields the ?rst lower bounds on width-restricted clause learning for formulas in 3-CNF.

上一篇：Human-Guided Machine Learning for Fast and Accurate Network Alarm Triage

下一篇：Community Detection in Social Networks through Community Formation Games

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...