资源论文MATHCHECK: A Math Assistant via a Combination of Computer Algebra Systems and SAT Solvers

MATHCHECK: A Math Assistant via a Combination of Computer Algebra Systems and SAT Solvers

2019-11-25 | |  39 |   34 |   0
Abstract We present a method and an associated system, called M ATH C HECK, that embeds the functionality of a computer algebra system (CAS) within the inner loop of a conflict-driven clause-learning SAT solver. SAT+CAS systems, a? la M ATH C HECK, can be used as an assistant by mathematicians to either counterexample or finitely verify open universal conjectures on any mathematical topic (e.g., graph and number theory, algebra, geometry, etc.) supported by the underlying CAS system. Such a SAT+CAS system combines the efficient search routines of modern SAT solvers, with the expressive power of CAS, thus complementing both. The key insight behind the power of the SAT+CAS combination is that the CAS system can help cut down the search-space of the SAT solver, by providing learned clauses that encode theory-specific lemmas, as it searches for a counterexample to the input conjecture. We demonstrate the efficacy of our approach on a long-standing open conjecture regarding matchings of hypercubes.

上一篇:Welfare Effects of Market Making in Continuous Double Auctions: Extended Abstract

下一篇:Practical 3D Tracking Using Low-Cost Cameras

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • A Mathematical Mo...

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

  • Rating-Boosted La...

    The performance of a recommendation system reli...