Solving satisfiability using inclusion-exclusion

Preprint English OPEN
Zaleski, Anthony;
(2017)
  • Subject: Mathematics - Combinatorics | Computer Science - Data Structures and Algorithms | 68W40, 68R01
    acm: TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES | ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
    arxiv: Computer Science::Symbolic Computation | Computer Science::Computational Complexity | Computer Science::Mathematical Software

Using Maple, we implement a SAT solver based on the principle of inclusion-exclusion and the Bonferroni inequalities. Using randomly generated input, we investigate the performance of our solver as a function of the number of variables and number of clauses. We also tes... View more
Share - Bookmark